Машина Тьюринга
на языке Python

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

На выходе машина напечатает:

[0, 0, 0, 1, 1, 1, 1, '0', '0']

Это та же лента, которую мы дали на входе, только на ней на одну единицу больше. 

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

Постановка задачи. 

Дан алфавит из двух символов: 0 и 1. Бесконечная лента заполнена нулями и только в одном месте находится строка из нескольких единиц (число их неизвестно). Дано, что в самом начале управляющее устройство (далее - УУ) находится где-то слева от строки с единицами. Машина должна найти на ленте эту строку и добавить справа от неё ещё одну единицу.

 

Задание станет совершенно понятно, если вы посмотрите на рисунок:

turing1.webp

Почему в формулировке задачи мы постановили, что УУ находится слева от строки с единицами, а не в произвольном месте ленты ? Дело в том, что, если бы мы были вынуждены искать единицы по всей ленте (то есть в обоих направлениях), задача усложнилась бы многократно! Более того, было бы крайне тяжело обойтись только двумя символами алфавита. Поэтому остановимся на гораздо более простой формулировке задачи, и попробуем разработать стратегию решения.

 

Естественно, что в самом начале УУ начинает двигаться вправо и сканировать содержимое клеток ленты. Если УУ видит в клетке ноль, оно оставляет всё как есть и делает один шаг вправо. Если УУ видит в клетке единицу, оно оставляет всё как есть и делает один шаг вправо. Постойте! В чём же разница между двумя действиями, которые совершает УУ в случае чтения нуля и в случае чтения единицы ? Верно - разницы в поведении УУ нет, но есть более существенная разница - в поведении самой Машины Тьюринга, вернее, программы, которая управляет УУ. Дело в том, что изначально наша Машина находится в некоем состоянии (назовём его состояние А), которое можно охарактеризовать так: ищи строку единиц справа от УУ. В тот момент, когда УУ считывает единицу, Машина переходит в состояние В, которое означает: а теперь ищи самую последнюю (самую правую) единицу в строке единиц. При этом УУ совершает те же самые действия, только находясь в другом состоянии.

 

Итак, находясь в состоянии B, машина продолжает двигаться вправо, сканируя ленту. Наконец, УУ обнаруживает в клетке ноль (это может случиться как на следующем ходу, так и через целый гугл клеток). Этот ноль означает, что строка единиц кончилась и пришло время добавить новую единицу. УУ заменяет этот ноль на единицу и останавливается. При этом, мы можем оставить машину в состоянии В, но более красивым вариантом будет перевести её в состояние С, который будет "тупиком" - это состояние будет означать остановку машины.

 

Задача выполнена. Теперь, чтобы построить управляющую таблицу (проще говоря - программу) Машины Тьюринга, призовём на помощь диаграмму, так называемый "конечный автомат":

turing2.webp

На этой диаграмме изображены три только что описанных состояния. Во многом она говорит сама за себя, и в объяснении нуждаются только подписи под стрелками перехода из одного состояния в другое. Так 0 -> 0 / Right обозначает: если УУ видит в клетке 0, оно должно заменить его на 0 и сдвинуться вправо. Таким образом, 0 -> 1 / Stop значит: если в клетке 0, замени его на 1 и не двигайся.

Всё предельно просто. Теперь нам осталось только перевести диаграмму состояний в таблицу управления и Машина Тьюринга, решающая поставленную задачу, готова!

 

А вот и таблица:

turing3.webp

Как видите, состояние С - это полный тупик. Машина ничего не меняет и никуда не двигается. Более того, из этого состояния нет выхода ни в какое другое.

 

И чтобы рассеять последние сомнения, приведём последовательность шагов и состояний, в которых будет пребывать наша Машина, решая поставленную задачу:

turing4.webp

Ещё раз та же программа, на этот раз с подробными комментариями: