История. Статья Тьюринга 1936 года

share the uri
  • История. Статья Тьюринга 1936 года

    Весной 1935 Тьюринг прослушал курс лекций по основаниям математики М. Ньюмана. В завершение курса были подробно рассмотрены сформулированные Д. Гильбертом на международном конгрессе 1928 года проблемы установления непротиворечивости, полноты и разрешимости аксиоматических теорий математики. Также была рассмотрена доказанная К. Гёделем в 1931 теорема о неполноте, из которой следовал отрицательный ответ на вопрос о возможности доказательства непротиворечивости и полноты достаточно богатых математических теорий. Однако все еще сохранялась надежда, что может существовать универсальный метод, который позволял бы по любому математическому утверждению в языке логики предикатов первого порядка установить, является оно доказуемым или нет. Это была остававшаяся открытой проблема разрешимости (Entscheidungsproblem). Именно она и привлекла внимание Тьюринга.

    В результате напряженной работы в конце 1935 – начале 1936 г. Тьюринг построил строгую логико-математическую модель того, что неформально можно описать как вычисление посредством механически детерминированного процесса. С помощью этой модели он доказал, что проблема разрешимости не имеет решения. Статья с подробным изложением полученных результатов была написана в апреле 1936 [Turing, 1936–1937], а опубликована в двух частях 30 ноября и 23 декабря 1936 [Copeland, 2004].

    Одновременно с Тьюрингом над этой же проблемой работал американский логик А. Чёрч. Средствами специально построенного λ-исчисления он доказал, что неразрешимые проблемы существуют [Church, 1936b] и связал это с поставленной Гильбертом проблемой разрешения [Church, 1936a]. Тьюринг узнал о работах Чёрча лишь в мае 1936 и в дополнении к своей статье, написанном в августе 1936, показал эквивалентность предложенного им понятия вычислимости и вычислимости в терминах λ-исчисления. Когда публикация Тьюринга вышла в свет, именно Чёрч первым ввел в научный обиход термин «машина Тьюринга» [Church, 1937].

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

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

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

    3. Тьюринг доказал неразрешимость проблемы остановки (halt problem), суть которой заключается в том, чтобы по описанию произвольной вычислительной машины (алгоритма) определить, завершится когда-нибудь производимый ею процесс вычисления или нет. Было показано, что неразрешимые математические проблемы существуют и конкретный их пример – проблема остановки. Была доказана неразрешимость проблемы появления на рабочей ленте конкретной машины Тьюринга конкретного символа (printing problem). Еще одно следствие существования неразрешимых проблем, открытых Тьюрингом, заключается в том, что не существует универсального метода, который позволял бы по произвольной программе проверить, действительно ли она производит именно те вычисления, для которых была составлена?

    4. Был предложен ряд аргументов в пользу того, что позже было названо «тезисом Тьюринга». Суть его заключалась в утверждении, что машины Тьюринга являются адекватной формализацией любых вычислений с финитными средствами, которые способен выполнить человек. Ранее Клини и Чёрч уже высказали предположения, что их формализации вычислимых функций средствами общерекурсивных функций и λ-исчисления адекватно представляют класс всех эффективно вычислимых функций, однако Гёдель не посчитал представленные аргументы достаточно убедительными и только после публикации Тьюринга согласился принять то, что в будущем получило название «тезиса Чёрча – Тьюринга».

    5. Было доказано, что сформулированная Гильбертом проблема разрешимости не имеет решения, т.е. не существует метода, который по произвольной формуле логики предикатов первого порядка мог дать ответ, выводима она из аксиом или нет.

  • Bibliography

  • Church A. A Note on the Entscheidungsproblem // The Journal of Symbolic Logic. 1936a. Vol. 1. No. 1. P. 40–41.
  • Church A. An Unsolvable Problem of Elementary Number Theory // American Journal of Mathematics. 1936b. Vol. 58. No. 2. P. 345–363.
  • Church A. Review // The Journal of Symbolic Logic. 1937. Vol. 2. No. 1. P. 42–43.
  • Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.
  • Hodges A. Alan Turing: The Enigma. L.; N. Y., 1983.
  • 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.
  • Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction // Proceedings of the London Mathematical Society – London Mathematical Society. 1938. Vol. S2-43. Iss. 6. P. 544–546.