Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
занимательное пособие по экспериментальной философии
Машина Тьюринга
на языке Python
Здесь мы создадим минималистическую машину Тьюринга на языке программирования Python, которая может выполнять любую заданную программу. Для примера мы дадим ей программу добавления единице к данному числу, представленному последовательностью единиц.
Вот эта машина и её вызов с программой и входной лентой в качестве параметров:
На выходе машина напечатает:
[0, 0, 0, 1, 1, 1, 1, '0', '0']
Это та же лента, которую мы дали на входе, только на ней на одну единицу больше.
Обратите внимание, что машина Тьюринга в этой программе, конечно, не совсем закончена: она не умеет работать с бесконечной лентой, и её алфавит состоит только из двух символов - 0 и 1. Но не будем слишком усложнять.
Программа в конце этой страницы снабжена подробными комментариями для желающих получше в ней разобраться.
Постановка задачи.
Дан алфавит из двух символов: 0 и 1. Бесконечная лента заполнена нулями и только в одном месте находится строка из нескольких единиц (число их неизвестно). Дано, что в самом начале управляющее устройство (далее - УУ) находится где-то слева от строки с единицами. Машина должна найти на ленте эту строку и добавить справа от неё ещё одну единицу.
Задание станет совершенно понятно, если вы посмотрите на рисунок:
Почему в формулировке задачи мы постановили, что УУ находится слева от строки с единицами, а не в произвольном месте ленты ? Дело в том, что, если бы мы были вынуждены искать единицы по всей ленте (то есть в обоих направлениях), задача усложнилась бы многократно! Более того, было бы крайне тяжело обойтись только двумя символами алфавита. Поэтому остановимся на гораздо более простой формулировке задачи, и попробуем разработать стратегию решения.
Естественно, что в самом начале УУ начинает двигаться вправо и сканировать содержимое клеток ленты. Если УУ видит в клетке ноль, оно оставляет всё как есть и делает один шаг вправо. Если УУ видит в клетке единицу, оно оставляет всё как есть и делает один шаг вправо. Постойте! В чём же разница между двумя действиями, которые совершает УУ в случае чтения нуля и в случае чтения единицы ? Верно - разницы в поведении УУ нет, но есть более существенная разница - в поведении самой Машины Тьюринга, вернее, программы, которая управляет УУ. Дело в том, что изначально наша Машина находится в некоем состоянии (назовём его состояние А), которое можно охарактеризовать так: ищи строку единиц справа от УУ. В тот момент, когда УУ считывает единицу, Машина переходит в состояние В, которое означает: а теперь ищи самую последнюю (самую правую) единицу в строке единиц. При этом УУ совершает те же самые действия, только находясь в другом состоянии.
Итак, находясь в состоянии B, машина продолжает двигаться вправо, сканируя ленту. Наконец, УУ обнаруживает в клетке ноль (это может случиться как на следующем ходу, так и через целый гугл клеток). Этот ноль означает, что строка единиц кончилась и пришло время добавить новую единицу. УУ заменяет этот ноль на единицу и останавливается. При этом, мы можем оставить машину в состоянии В, но более красивым вариантом будет перевести её в состояние С, который будет "тупиком" - это состояние будет означать остановку машины.
Задача выполнена. Теперь, чтобы построить управляющую таблицу (проще говоря - программу) Машины Тьюринга, призовём на помощь диаграмму, так называемый "конечный автомат":
На этой диаграмме изображены три только что описанных состояния. Во многом она говорит сама за себя, и в объяснении нуждаются только подписи под стрелками перехода из одного состояния в другое. Так 0 -> 0 / Right обозначает: если УУ видит в клетке 0, оно должно заменить его на 0 и сдвинуться вправо. Таким образом, 0 -> 1 / Stop значит: если в клетке 0, замени его на 1 и не двигайся.
Всё предельно просто. Теперь нам осталось только перевести диаграмму состояний в таблицу управления и Машина Тьюринга, решающая поставленную задачу, готова!
А вот и таблица:
Как видите, состояние С - это полный тупик. Машина ничего не меняет и никуда не двигается. Более того, из этого состояния нет выхода ни в какое другое.
И чтобы рассеять последние сомнения, приведём последовательность шагов и состояний, в которых будет пребывать наша Машина, решая поставленную задачу:
Ещё раз та же программа, на этот раз с подробными комментариями: