Тезис Тьюринга

То, что называют тезисом Тьюринга, было высказано им как гипотеза о том, что «вычислимые в рамках его математической модели действительные числа включают все числа, которые в принципе способен вычислить человек». Доказать эту гипотезу невозможно, но в ее подтверждение он привел ряд аргументов.

Во-первых, это интуитивное представление о вычислении. Оно заключалось в анализе действий воображаемого человека-вычислителя и переходе к формализации в терминах машинных операций.

Во-вторых, Тьюринг показал, что различные модификации его модели не приводят к изменению множества вычислимых функций.

В-третьих, он также показал, как с произвольной точностью до любого знака после запятой можно вычислить любые числа, являющиеся корнями алгебраических уравнений, числа e и π, являющиеся пределами последовательностей $\text{e=}1+1+1/2\text{!+}1/3\text{!+}1/5!\dots$  и $\text{π=}4\times \left(1-1/3+1/5\dots \right)$ , и др.

То, что в названии статьи и в основных примерах речь идет о вычислении бесконечных разложений действительных чисел, не должно заслонять сути проделанной Тьюрингом работы. Во многих других примерах он показал, как построить машины, способные производить и другие символьные вычисления.

Уже после публикации работы Тьюринга были проведены дополнительные исследования, призванные подтвердить или опровергнуть данный тезис. Вместо машины Тьюринга с бесконечной лентой в обе стороны были проанализированы машины с бесконечной лентой лишь в одну сторону. Оказалось, что такое ограничение не приводит к изменению множества вычислимых функций. Были проанализированы машины Тьюринга с несколькими сканирующими, считывающими и печатающими головками. Множество вычислимых функций не изменилось. Были рассмотрены варианты с несколькими лентами и различными по величине наборами символов, но результат остался прежним. С тех пор были предложены другие подходы к аксиоматизации эффективно вычислимых функций. Наиболее известны нормальные алгорифмы Маркова [Марков, Нагорный, 1984] и машины с неограниченными регистрами [Катленд, 1983]. Было доказано, что и для них множество вычислимых функций совпадает с множеством функций, вычислимых на машинах Тьюринга. Более подробно тезис Тьюринга и аргументы в его пользу анализируются в работе [Клини, 1957, c. 317-342].

В настоящее время тезис Тьюринга имеет разные формулировки, но суть их одна – универсальная машина Тьюринга может выполнить любое вычисление, которое способен выполнить человек-вычислитель. При этом значение тезиса Тьюринга выходит далеко за рамки арифметики и не сводится лишь к операциям с числами, поскольку с их помощью могут быть закодированы и представлены операции над любыми конструктивными объектами.