Машина Тьюринга M, содержащая любое количество ленточных символов, может быть смоделирована одним M', содержащим всего три ленточных символа: {0, 1, B} (B = Пусто).
Можно ли смоделировать М с помощью М", который имеет только два символа ленты, скажем, {1, В}?
Первый шаг — переход от любой ТМ к ТМ только с единицами и нулями — не так сложен, как вы думаете, но и не так прост, как говорят все остальные. Идея состоит в том, чтобы разработать двоичное кодирование фиксированной длины для каждого символа в алфавите. Затем вы обновляете элемент управления с конечным состоянием, чтобы на каждом шаге TM сканировал соответствующее количество битов, решал, в каком направлении двигаться и какой символ записывать, записывал двоичное представление нового символа и повторял. Этого можно добиться, имея ОГРОМНЫЙ элемент управления с конечным числом состояний, и я оставлю подробности читателю, так как очень педантично рассказывать, как это работает. :-). Следует отметить одну деталь: в этой конструкции вы представляете пустой символ как последовательность пробелов той же длины, что и изобретенные вами двоичные символы.
Чтобы реализовать TM, используя только 1 и B, вы используете аналогичный трюк. Во-первых, уменьшите TM, чтобы использовать только 1, 0 и B. Мы снова уменьшим набор символов на меньший, но должны быть немного умнее, потому что на ленте бесконечно много пробелов. Это. Мы будем использовать следующую кодировку:
Когда мы запускаем ТМ, используя эту схему кодирования, если мы когда-либо пройдем мимо конца ранее просмотренной ленты, мы встретим бесконечно много пустых символов, которые, к счастью, соответствуют нашей кодировке пустого символа.
Единственная проблема заключается в том, как закодировать ввод в этот новый TM, чтобы мы могли преобразовать его в указанный выше формат. Поскольку во вводе TM не может быть пробелов, ввод должен быть закодирован в унарном коде. Затем мы оговариваем, что для любой двоичной строки w старой машины входными данными новой машины должно быть унарное кодирование числа 1w. Затем у нас есть первый шаг машины — преобразовать унарную кодировку в указанную выше двоичную кодировку. Это можно сделать с помощью всего двух символов, но детали очень сложны, и я снова собираюсь их использовать. Если хотите, можете уточнить детали.
Надеюсь это поможет!
Первый из них прост, представьте себе компьютер, двоичный файл....
В первом вы можете закодировать каждый символ в представлении 0,1.
Во втором вы можете сделать 2 вещи:
Думайте о B как о 0 ... неважно, как вы это называете ... и тогда у вас есть машина 0,1, и вы можете кодировать все, что хотите.
Закодируйте символы как серию единиц, разделенных буквой B. N-й символ будет содержать N единиц.
