§ 13.3. Вычисления на машинах Тьюринга

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

Условимся, как мы будем представлять натуральные числа и нуль на ленте машины Тьюринга. Воспользуемся кодом, согласно которому числа записываются в натуральной («единичной») системе счисления и число представляется расположенными подряд символами 1 в ячейках ленты, так что нуль — один символ 1, единица — два символа 1 и т. д.

Будем говорить, что два числа расположены рядом, если между записями кодов этих двух чисел имеется ровно одна пустая ячейка. В табл. 13.31 рядом с числом 3 справа расположено число 0, а рядом с числом 0 справа — число 2.

Таблица 13.31

В этом случае мы скажем, что числа 3, 0 и 2 расположены подряд.

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

Вспомним, что в нашей «конструкции» машины Тьюринга имеется самая левая (первая) ячейка ленты. Оставим пустыми первые две ячейки ленты, а начиная с третьей ячейки, запишем в принятом нами коде чисел подряд в том же порядке, в котором пронумерованы независимые переменные. В табл. 13.32 приведен пример подобной записи при

Таблица 13.32.

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

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

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

все ячейки, расположенные правее той, напротив которой находится головка, пусты.

Пусть Т начинает работать, отправляясь от описанной начальной ситуации.

Мы скажем, что Т вычисляет функцию переменных, если, каковы бы ни были числа существует такой момент времени, в который

а) машина Т достигнет состояния покоя

б) на ленте будет представлена система чисел , где , которую головка машины воспринимает в стандартном положении;

в) все ячейки, расположенные правее той, напротив которой находится головка, пусты.

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

Приведем пример, поясняющий определение вычислений на машине Тьюринга. Пусть Тогда при начальная ситуация на ленте должна быть такой, как в табл. 13.32; ситуация после остановки машины представлена табл. 13.33.

Таблица 13.33

Теперь мы в состоянии показать, что, какова бы ни была рекурсивная функция, можно построить машину Тьюринга, вычисляющую эту функцию. Для того, чтобы подобное доказательство провести, достаточно показать, что существуют машины Тьюринга, способные вычислять функцию следования, функции-константы и функции-тождества, а также машины, производящие операцию суперпозиции, вычисление по индукции и взятие оператора наименьшего числа (см. § 12.10).

Предварительно нам понадобится ввести в рассмотрение еще несколько специальных машин Тьюринга.

Машина строится с помощью умножения и итерации из машин , описанных в § 13.1, следующим образом:

Основная таблица этой машины имеет вид табл. 13.34.

Машина Р начинает работать, воспринимая самую правую заполненную ячейку представления какого-либо числа. Результатом ее работы является ситуация, в которой это число «перегоняется» налево и ставится рядом с ближайшим слева числом. Рассмотрение табл. 13.34 показывает, что тот же самый результат может дать несколько другая машина, имеющая не 12, а 6 состояний, основной таблицей которой является табл. 13.35.

Таблица 13.34

Машина Р

Таблица 13.35

Машина Р

Поскольку нам в дальнейшем безразлично устройство машины, а важен лишь результат ее работы, то, говоря о машине Р, можно иметь в виду как табл. 13.34, так и табл. 13.35.

Вариант работы машины Р представлен в соответствии с табл. 13.35 в табл. 13.36.

Машина строится из машин Н, F, Е, D, С, В, А (§ 13.1) с помощью умножений и итерации следующим образом:

Таблица 13.36

Таблица 13.37

Где индекс наверху обозначает степень соответствующей машины. В частности,

Воспринимая в начальный момент времени систему чисел в стандартном положении, машина печатает справа от представления чисел первое из этих чисел (т. е. ) и останавливается, воспринимая в стандартном положении систему чисел . Если же машина воспринимает в начальный момент времени в стандартном положении систему чисел , где , то она отпечатает справа от этой системы чисел число и остановится, воспринимая систему . В качестве примера вариант работы машины изображен в табл. 13.37. Буквы справа здесь означают, какие из машин, «составляющих» , ответственны за переход от одной ситуации на ленте к другой. Символы означают состояния покоя машины Е.

Можно показать, что степень машины копирует систему чисел , воспринятую в стандартном положении, справа, так что результатом работы будет система чисел , воспринимаемая в стандартном положении. Начальная и конечная ситуации работы машины при изображены в табл. 13.38.

Таблица 13.38

Машина делает «почти то же самое», что и машина , т. е. копирует систему справа, но не рядом, а с одним промежутком (т. е. между числами расположена не одна, а две пустые ячейки). Машина строится по формуле

Начальная и конечная ситуации работы машины при изображены в табл. 13.39.

Таблица 13.39

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

I. Функцию следования вычисляет машина . Действительно, воспринимая в начальный момент число в стандартном положении, машина напечатает правее числа и остановится в стандартном положении системы чисел ), т. е., по определению понятия «вычисление», вычислит . Работа машины при изображена в табл. 13.40.

II. Функцию-константу вычисляет машина . Пример работы машины для приведен в табл. 13.41.

III. Функцию тождества вычисляет машина Действительно, эта машина правее системы чисел печатает число справа, т. е. .

Дальнейшее доказательство ведем по индукции по глубине рекурсивного описания рекурсивной функции. Функции I, II, III имеют по определению глубину нуль.

Таблица 13.40

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

Таблица 13.41

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

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

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

Такой машиной является

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

Машина останавливается только в том случае, когда таково, что выполнено требование .

Приведем примеры вычисления по индукции и взятия оператора наименьшего числа, поясняющие схемы машин V и VI.

Таблица 13.42 (см. оригинал)

Таблица 13.43 (см. оригинал)

Пример вычисления по индукции. Пусть

так

В табл. 13.42 машина М вычисляет значение . Индексы означают состояния машины Е.

Идея вычисления заключается в повторном вычислении функции ПРИ соответствующем контроле того, сколько раз это вычисление проведено.

Результат вычисления: .

Пример взятия оператора наименьшего числа. Пусть , так что

и надо вычислить . Работа машины представлена в табл. 13.43.

Идея вычисления заключается в определении последовательных значений и т. д. до тех пока . Результат вычисления: .

Заметим еще, что все машины, выполняющие I — VI, сконструированы так, что они никогда не заходят за левый край ленты.

Таким образом, мы показали, что любая рекурсивная: функция может быть вычислена на машине Тьюринга. Можно показать, что на машинах Тьюринга вычисляются только рекурсивные функции. Этот факт доказывается при помощи гёделизации ситуаций на ленте и проверки того обстоятельства, что любое изменение ситуации может быть описано с помощью рекурсивных функций (см. доказательство в [42]).

В силу эквивалентности понятий «рекурсивная функция» и «функция, вычислимая на машине Тьюринга», а также в силу тезиса Чёрча можно дать и следующее определение понятия алгоритм: алгоритмом называется любая процедура, сводящаяся к вычислению значений целочисленной функции на соответствующей машине Тьюринга.