Машины Тьюринга в алфавите {0, 1}

В качестве первого примера моделирования рассмотрим машины Тьюринга, алфавит которых состоит из двух символов. Обозначим эти элементы 0 и 1 и будем считать символ 0 пустым.

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

Задача 4.6. Докажите, что для любых двух слов u, v € А* существует машина Тьюринга с алфавитом Л, результаты работы которой на словах и, v различны.

Однако инъективности отображения недостаточно. Рассмотрим такое отображение слов в алфавите {(), 1,2,3} в двоичные слова:

Это отображение инъективно. Но возникает другая трудность: в определении входа указано, что первый и последний символы входного слова должны быть непустыми. Кодировки слов 1 и 2 не удовлетворяют этому свойству. Поэтому потребуем, чтобы коды всех слов должны начинались и заканчивались на 1.

Приведём пример подходящей кодировки слов в алфавите А = {ао, • • •,a_n-i} (без ограничения общности, считаем, что ао = Л является пустым символом). Кодом символа а* будем считать слово, а кодом слова … сц_к — конкатенацию кодов символов.

c (aj₁)c (ai₂)… c (ai_k). Код любого символа имеет длину п + 7, поэтому это кодирование равномерно — слову w G А* длины к оно сопоставляет слово c (w) G {0,1}* длины (п + 7)к.

Задача 4.7. Проверьте, что описанное кодирование обладает следующими свойствами: (а) оно инъективно; (б) код любого слова начинается и заканчивается на 1.

В качестве отображения декодировки, которое нужно для определения эквивалентности вычислительных моделей, возьмём (частично определённое) обратное к отображению кодировки.

Теперь можно уточнить утверждение о моделировании произвольной машины Тыоринга машиной Тыоринга в алфавите {0,1}.

Машина Тыоринга N в алфавите {(), 1} моделирует машину Тыоринга М = (A, Q, Q/, S, qo, А), где А = п, если она удовлетворяет следующему свойству: на входе вида c (w), где w — вход машины М, результатом работы МТ N является с (а), где и — результат работы машины М на входе w.

Построить такую машину довольно просто. Её множество состояний имеет вид Q х {О, 1}^п+7 х Q'. Другими словами, в «оперативной памяти» машины N поддерживается информация о состоянии моделируемой машины М и о текущем символе моделируемой машины (см. пояснения на с. 169). Управление работой N осуществляется состояниями из множества Q'.

Начальным состоянием машины N является состояние (<70,0^П, q'₀), финальными — состояния вида (</, w. г/), где qeQf, tiq'

Мы опишем работу машины N как выполнение последовательности итераций. Перед началом каждой итерации будут выполнены условия корректности: машина находится в состоянии вида (q, w, q'₀); на ленте записано слово с (г/.), которое является кодом слова и? А* ; головка машины находится над самым левым символом кода некоторого символа а слова и. Каждая итерация занимает не более 3(п + 7) + + 2 тактов работы, каждому из которых соответствует своё собственное состояние из множества Q'. Как будет видно, вариантов каждого такта не более трёх, так что общий размер множества Q' не превосходит 9(тг + 7) + 6.

Итерация состоит из следующих шагов (предполагаются выполненными условия корректности перед началом итерации):

• • Прочитать в «оперативную память» текущий символ на ленте. Для этого машина делает п —1−7 тактов работы, каждый раз запоминая в памяти прочитанный с ленты символ и сдвигаясь вправо (кроме последнего такта). В конце этого шага головка находится над последним символом кода текущего символа. Состояние машины в этот момент имеет вид (q, c (a)^q'_n+7).
• • Изменить текущий символ в соответствии с таблицей переходов машины М. Этот шаг также требует п + 7

тактов работы: машина движется справа налево, записывая на очередное место очередной символ кода символа о!, который машина М пишет, когда находится в состоянии q и видит символ а.

• • Изменить положение головки. После предыдущего шага головка будет находиться над крайним левым символом кода символа. Если в таблице переходов М в строке (a,q) записана, инструкция «остаться на месте», то ничего делать не нужно. Если записана инструкция «сдвинуться влево», то нужно выяснить, записан ли слева код какого-нибудь символа (для этого достаточно сделать шаг влево и проверить, записана ли в этой ячейке 1). После этого нужно сделать п Н- 7 тактов работы, сдвигая головку влево (и записывая при необходимости биты кода пустого символа, в этом случае необходим ещё один дополнительный такт работы для записи последнего бита, после которого машина остаётся на месте). Аналогичные действия происходят при обработке инструкции «сдвинуться вправо».
• • Изменить первую компоненту состояния в соответствии с таблицей переходов машины М, а третью сделать равной q'₀. После этого все условия корректности становятся выполнен н ы м и.

Фактически, мы доказали следующую теорему.

Теорема 4.38. Для любой машины Тьюринга М существует машина в двухбуквенном алфавите М', моделирующая, работу М.

Задача 4.8 («МТ с засорившейся головкой»). МТЗГ это такая машина Тьюринга, которая может писать на ленту только символ *. Формально это условие можно выразить так: если S (a, q) = (а', г, </), то а' € {а, *}. Докажите, что для любой МТ Л/, алфавит которой не содержит *, существует такая МТЗГ М', что на любом входном слове w машина М останавливается тогда и только тогда, когда на этом входе останавливается машина M^f.