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

share the uri
  • Тезис Тьюринга

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

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

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

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

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

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

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

  • Bibliography

  • Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.
  • Turing A.M. Computability and λ-definability // The Journal of Symbolic Logic. 1937. Vol. 2. No. 4. P. 153–163.
  • Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.
  • Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.
  • Клини С.К. Введение в метаматематику. М., 1957.
  • Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1984.