В математике тезис Черча-Тьюринга утверждает, что любую вычислимую функцию можно задать машиной тьюринга.
Этот тезис (как и эквивалентные ему тезисы Маркова, Поста и т.д.) и в математике нельзя доказать. По тривиальной причине: "любая вычислимая функция" в этом тезисе - не математическое понятие, поскольку не имеет математического определения. Доказать что-либо математически в такой ситуации нельзя. В действительности этот тезис просто утверждает, что математическая формализация наших интуитивных представлений о вычислимости, представленная машиной Тьюринга, является адекватной. В это можно верить, а можно и не верить. Например, в интуиционистском направлении математики представление о вычислимости более широкое (Справочная книга по математической логике. Часть IV. Теория доказательств и конструктивная математика. Москва, "Наука", 1983. Глава 5. А.С.Трулстра. Аспекты конструктивной математики. § 4. Реализуемость и тезис Чёрча.).
Что касается "вычислимости" физическим устройством... Ну, предположим, у нас есть некоторое количество свободных нейтронов в сосуде (ситуация является физически реализуемой: сосуд из диамагнитного материала и очень низкая температура). Это устройство "вычисляет" моменты распада нейтронов. Мои представления о квантовой физике заставляют меня думать, что никакая машина Тьюринга не сможет вычислить эти моменты.