Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
занимательное пособие по экспериментальной философии
Машина Тьюринга
на языке 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 и не двигайся.
Всё предельно просто. Теперь нам осталось только перевести диаграмму состояний в таблицу управления и Машина Тьюринга, решающая поставленную задачу, готова!
А вот и таблица:
Как видите, состояние С - это полный тупик. Машина ничего не меняет и никуда не двигается. Более того, из этого состояния нет выхода ни в какое другое.
И чтобы рассеять последние сомнения, приведём последовательность шагов и состояний, в которых будет пребывать наша Машина, решая поставленную задачу:
Ещё раз та же программа, на этот раз с подробными комментариями: