Истоки машины Тьюринга

Алан Тьюринг разработал концепцию машины Тьюринга в 1930-х годах, задолго до того, как технология развилась настолько, чтобы создать машины, известные нам сегодня. В действительности Тьюринг исходил из того, как люди производят вычисления при помощи карандаша и бумаги. Его целью была разработка модели, при помощи которой можно было бы изучать ограничения вычислительных процессов. Он приступил к работе вскоре после публикации в 1931 году знаменитой статьи Гёделя, раскрывающей пределы вычислительных систем, когда основные силы исследователей были направлены на изучение этих границ. В том же году, когда Тьюринг представил свою модель (1936), Эмиль Пост представил другую модель (ныне известную как система продукций Поста), которая должна была обладать теми же способностями, что и модель Тьюринга. Доказывая проницательность первых исследователей, их модели вычислительных систем до сих пор являются ценными инструментами в исследовании вычислительной техники.

У нашей машины есть состояния Начало, Прибавить, Перенос, Переполнение, Возврат и Останов. Действия, соответствующие каждому из этих состояний, и содержимое текущих ячеек перечислены в табл. 11.1. Мы предполагаем, что машина всегда начинает работу из состояния Начало.

Пусть эта машина работает на содержащей значение 5 ленте, приведенной ранее. Когда машина находится в начальном состоянии, а в текущей ячейке записана * (как в нашем случае), таблица приказывает переписать *, переместить головку считывания-записи на одну ячейку влево и перейти в состояние Прибавить. После выполнения этих действий машину можно описать следующим образом:

Состояние машины = Прибавить

Для продолжения работы посмотрим в таблице, что следует делать в состоянии Прибавить с единицей в текущей ячейке. Таблица говорит нам заменить 1 в текущей ячейке на 0, передвинуть головку считывания-записи на одну ячейку влево и войти в состояние Перенос. Конфигурация машины:

Мы снова обращаемся к таблице за дальнейшими указаниями и обнаруживаем, что в состоянии Перенос, если в текущей ячейке содержится 0, необходимо заменить 0 на 1, переместить головку считывания-записи на одну ячейку вправо и войти в состояние Возврат.

Конфигурация машины после этого:

В этой ситуации таблица говорит нам, что следует заменить 0 в текущей ячейке на 0, передвинуть головку считывания-записи на одну ячейку вправо и остаться в состоянии Возврат. Следовательно, машина переходит в состояние:

Теперь, согласно таблице, следует переписать звездочку в текущей ячейке и войти в состояние Останов. Таким образом, машина останавливается в следующей конфигурации (теперь символы на ленте представляют значение 6, как мы и хотели):

Тезис Черча-Тьюринга

Машину Тьюринга из предыдущего примера можно применять для вычисления функции, известной как функция следования, которая каждому неотрицательному целому входному значению п ставит в соответствие выходное значение п + 1. Необходимо всего лишь поместить входное значение в бинарной форме на ленту машины, запустить машину, дождаться ее остановки и считать выходное значение с ленты. Функция, которую можно вычислить подобным образом на машине Тьюринга, называется вычислимой по Тьюрингу (Turing computable).

Предположение Тьюринга заключалось в том, что вычислимые по Тьюрингу функции являются вычислимыми функциями. Другими словами, он считал, что вычислительная мощь машин Тьюринга равна вычислительным способностям любой алгоритмической системы, или, что то же самое, что (в противоположность таким подходам, как таблицы или алгебраические формулы) концепция машины Тьюринга является средой, в которой можно выразить решения всех вычислимых функций. Сегодня это предположение называют тезисом Черча—Тьюринга (Church-Turing thesis), указывая на вклад, сделанный Аланом Тьюрингом и Алонзо Черчем. С момента появления первой работы Тьюринга было собрано множество подтверждений этого тезиса, и сегодня тезис Черча-Тьюринга является общепринятым. То есть считается, что вычислимые функции и функции, вычислимые по Тьюрингу, — это одно и то же.

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