Как заставить свой компьютер эмулировать компьютер.

Хотя у вас может не быть доступа к физической машине Тьюринга, это не должно помешать вам смоделировать машину Тьюринга с помощью… вашего компьютера! Я расскажу о том, как работают машины Тьюринга, и о коде Python, чтобы построить простую машину для проверки предполагаемых палиндромов. Я знаю, что программы, которые проверяют палиндромы, являются обычным упражнением для новичков в программировании, и что вы можете просто проверить их в Интернете или даже скопировать код на своем любимом языке. Однако давайте представим, что в глубине души вы действительно хотели бы использовать для этой задачи машину Тьюринга.

Эта статья вдохновлена ​​главой 5 книги Перспективы вычислений Роберта Героха — Amazon.

Вы можете найти полный код на GitHub здесь.

Что такое машина Тьюринга?

Машина Тьюринга состоит из трех частей:

  1. Лента.
  2. Пишущая головка
  3. Состояние машины.

Лента разделена на последовательность квадратов, в каждом из которых может храниться один символ, принадлежащий к данному набору символов.

Это не очень ответило

Чем интересны машины Тьюринга? Вы определенно уже слышали о них, поэтому давайте просто быстро скопируем это из собственных слов Тьюринга и оставим дальнейшие подробности в главе Героха, упомянутой выше.

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

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

Как работают машины Тьюринга?

Машина работает на основе таблицы правил. На любом заданном шаге записывающая головка находится над каким-то квадратом на ленте. В этот момент машина: (1) считывает этот квадрат ленты и (2) считывает состояние, в котором находится машина. Затем машина просматривает таблицу правил, чтобы определить: (1) какой новый символ нужно записать , (2) в какое новое состояние перейти и (3) в каком направлении, на одну клетку влево или вправо, должна двигаться голова. Конечно, машине разрешено печатать один и тот же символ и сохранять то же состояние.

Когда машина закончила? Для этой цели зарезервировано специальное состояние. Как только машина входит в это состояние, программа завершает работу.

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

Реализация машины Тьюринга

Машина Тьюринга состоит из трех элементов (которые мы реализуем следующим образом):

  1. состояние (строка с именем state)
  2. записывающая головка (целое число с именем write_head)
  3. лента (список с именем tape_list)

В качестве простой реализации напишем класс с этими элементами следующим образом:

Далее мы будем работать с таблицей правил, определенной в updateMachine.

Таблица правил

А таблица правил? Таблица, которую необходимо реализовать, приведена ниже — под ней следует пояснение.

Это требует некоторого объяснения! Начнем с определения состояний:

  • q1 — исходное состояние. Здесь мы читаем символ n, который соответствует n-му символу в списке символов (при условии, что он не равен нулю). Эта информация «сохраняется» в состоянии при переходе в соответствующее состояние pn.
  • pn — состояние после прочтения n-го символа изначально — теперь идем вправо и ищем конец строки, отмеченный нулем.
  • rn — состояние после нахождения нуля в конце строки — теперь сравним последний символ строки. Если это палиндром, то он должен быть таким же, как n-й символ, который мы читаем в начале, и мы переходим в состояние q2. в противном случае перейдите к состоянию qn, что означает «нет, это не палиндром».
  • q2 — состояние после успешного сравнения последнего символа в строке — теперь идем влево и ищем начало строки, отмеченное нулем. Перезапустите цикл, перейдя к q1.

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

Во-первых, слово «из», которое не является палиндромом:

В последней строке, поскольку «f» не был 15-м символом алфавита (а именно «o», который мы считывали на первом шаге), машина переходит в состояние qn, правильно указывая, что «of» не является палиндром.

Во-вторых, символы «bbb», которые являются палиндромами:

Это было ужасно долго, но это сработало! Обратите внимание, что для переключения с p2 на r2 во второй раз при чтении нуля использовалось наше дополнительное условие * в таблице правил.

Или, что угодно, это работает.

Что касается кода, опять же, не усложняйте его и используйте операторы if и elif:

Настройка ввода/вывода

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

Запуск кода

Наконец, давайте запустим код! Опять же, мы обманули и обращаемся к состоянию на каждой итерации, чтобы проверить, завершилась ли программа (состояние qn или qy). Однако вы легко можете представить себе печать на ленте специального символа для обозначения результата при желании (оставим это как «упражнение»). Создайте файл с именем test.py с содержимым:

Запуск этого дает:

> python test.py hello
Checking: hello
- - -
q1 0 ['h', 'e', 'l', 'l', 'o', 0]
p7 1 [0, 'e', 'l', 'l', 'o', 0]
p7 2 [0, 'e', 'l', 'l', 'o', 0]
p7 3 [0, 'e', 'l', 'l', 'o', 0]
p7 4 [0, 'e', 'l', 'l', 'o', 0]
p7 5 [0, 'e', 'l', 'l', 'o', 0]
r7 4 [0, 'e', 'l', 'l', 'o', 0]
qn 3 [0, 'e', 'l', 'l', 'o', 0]
- - -
hello is NOT a palindrome! Steps: 7

и:

Checking: ooo
- - -
q1 0 ['o', 'o', 'o', 0]
p14 1 [0, 'o', 'o', 0]
p14 2 [0, 'o', 'o', 0]
p14 3 [0, 'o', 'o', 0]
r14 2 [0, 'o', 'o', 0]
q2 1 [0, 'o', 0, 0]
q2 0 [0, 'o', 0, 0]
q1 1 [0, 'o', 0, 0]
p14 2 [0, 0, 0, 0]
r14 1 [0, 0, 0, 0]
q2 0 [0, 0, 0, 0]
q1 1 [0, 0, 0, 0]
qy 2 [0, 0, 0, 0]
- - -
ooo is a palindrome! Steps: 12

Последние мысли

Это определенно был самый утомительный способ проверки палиндромов из когда-либо придуманных! Но волшебство в том, что нет предела тому, что вы можете реализовать с помощью машины Тьюринга, пока на вашем компьютере не закончится память.