Моделирование машины Тьюринга с помощью только двух символов на ленте

Теперь покажем, что можно также построить машину С, работающую подобно любой заданной машине Тьюринга А и использующую только два символа 0 и 1 на своей ленте; один из них, например 0, служит символом пустого квадрата. Пусть по-прежнему заданная машина А имеет символов и внутренних

состояний. Пусть I — наименьшее целое число, для которого Тогда символам машины А можно сопоставить двоичные последовательности длины таким образом, что различным символам будут соответствовать различные последовательности. При этом пустому символу машины А ставится в соответствие последовательность из I нулей. Машина С будет работать с двоичными последовательностями. Элементарная операция машины А будет соответствовать в машине С переходу считывающей головки на квадратов вправо (с сохранением считанной информации во внутреннем состоянии головки), затем обратному переходу на квадратов влево, записи новых символов по пути и, наконец, движению вправо или влево на I квадратов в соответствии с движением считывающей головки машины А. В течение этого процесса состояние машины А, конечно, сохраняется и в машине С. Замена старого состояния новым происходит в конце операции считывания.

Формально машина С строится так. Состояниям машины А ставятся в соответствие состояния машины С (последние будут встречаться, когда машина С начинает операцию, считывая первый символ в двоичной последовательности длины Для каждого из этих определим два состояния и Та. Если машина С находится в состоянии и читает символ О, то она движется вправо и переходит в состояние Если она читает 1, то движется вправо и переходит в состояние Таким образом, с помощью этих двух состояний машина запоминает, каким был первый символ двоичной последовательности. Для каждого из этих определим опять по два состояния: Если, например, машина находится в состоянии и читает символ 0, то она переходит в состояние Таким образом, с помощью этих состояний запоминается начальное состояние и два первых символа, прочитанных в процессе работы машины. Продолжим такое построение состояний вплоть до шагов, получив в итоге состояний. Эти состояния можно обозначить через

Если машина находится в одном из этих состояний ) и читает 0 или 1, то она движется вправо и 0 или 1 делается дальнейшим индексом состояния. Когда машина читает последний символ последовательности длины Теперь правила операций зависят от конкретных правил машины А. Определим два новых множества состояний, которые несколько похожи на введенное выше множество состояний Т, но соответствуют не считыванию, а записи:

Последовательность соответствует некоторому символу машины А. Предположим, что, если машина А читает этот символ и находится в состоянии то она записывает символ, соответствующий двоичной последовательности переходит в состояние и движется, скажем, вправо. Тогда по определению машина С, будучи в состоянии и читая символ переходит в состояние записывает символ и движется влево. В любом из состояний машина С записывает движется влево и переходит в состояние Посредством этого процесса двоичная последовательность, соответствующая новому символу, записывается вместо старой двоичной последовательности. При эта запись заканчивается на символе Остается только передвинуть считывающую голову на I квадратов вправо или влево в зависимости от того, находится ли машина в состоянии или в состоянии Это делается с помощью множеств состояний состоянии машина записывает движется вправо и переходит в состояние . В каждом из состояний машина продолжает движение вправо, не записывая ничего и переходя в состояние со следующим по величине индексом, пока не будет достигнуто последнее состояние Таким образом, вызывает движение вправо и состояние Наконец, состояние приводит после движения вправо — к состоянию завершая тем самым цикл. Аналогично, приводит к движению влево и состоянию дает движение влево и наконец дает движение влево и

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

Машина С имеет самое большее состояний Т, самое большее состояний и состояний , наконец, состояний и V. Таким образом, всего требуется не более чем состояний. Так как то эта верхняя оценка числа состояний меньше, чем , что в свою очередь заведомо меньше, чем

Полученные нами результаты вместе с интуитивными соображениями подсказывают, что можно заменять символы состояниями и обратно (в некоторых пределах), не изменяя намного произведения При переходе к двум состояниям произведение возрастает

приблизительно в восемь раз. При переходе к двум символам произведение возрастает приблизительно в шесть раз, но не более чем в восемь раз. Эти «коэффициенты потерь» - 6 и 8 — вызваны, вероятно, нашим методом микромоделирования, при котором каждая элементарная операция машины А моделируется в машине В. Если конструировать машину В, заботясь лишь о том, чтобы она имела те же вычислительные возможности в широком смысле, что и машина А, то произведение изменилось бы значительно меньше. Во всяком случае, число логических элементов (например, реле), необходимых для физической реализации машины, является небольшим постоянным кратным (приблизительно двукратным в случае реле) двоичного логарифма произведения и потому коэффициент или 8 потребует лишь немногих дополнительных реле.

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