Первый шаг - перейти от любой ТМ к ТМ только с единицами и нулями - не так сложно, как вы думаете, но не так просто, как говорят все остальные.Идея состоит в том, чтобы разработать двоичное кодирование фиксированной длины для каждого из символов в алфавите.Затем вы обновляете управление в конечном состоянии, чтобы на каждом шаге ТМ сканировал соответствующее количество битов, решал, какой путь и какой символ записать, записывает двоичное представление нового символа и повторяет.Это можно сделать, имея ОГРОМНОЕ конечное управление, и я оставлю подробности читателю, потому что очень педантично разбираться, как это работает.:-).Одна деталь, на которую следует обратить внимание, состоит в том, что в этой конструкции вы представляете пустой символ в виде последовательности пробелов той же длины, что и изобретенные вами двоичные символы.
Чтобы реализовать TM, используя только 1 и B, вы используете аналогичныйтрюк.Во-первых, уменьшите ТМ, чтобы использовать только 1, 0 и B. Мы снова уменьшим набор символов на меньший, но нам нужно будет быть немного более умным с тем, как мы это делаем, потому что на ленте бесконечно много пробелов.Это.Мы будем использовать следующую кодировку:
- 11 кодирует число 1
- 1B кодирует число 0
- BB кодирует пробел.
Когда мы запускаем TM, используя эту схему кодирования, если мы когда-нибудь пройдем конец ранее посещенной ленты, мы встретим бесконечно много пустых символов, которые, к счастью, соответствуют нашему кодированию пустого символа.
Единственная проблема заключается в том, как закодировать входные данные для этой новой ТМ, чтобы мы могли преобразовать их в указанный выше формат.Поскольку пробелы не могут появиться на входе TM, вход должен быть закодирован в унарном виде.Затем мы оговариваем, что для любой двоичной строки w старой машины входом для новой машины должна быть унарная кодировка числа 1w.Затем у нас есть первый шаг машины для преобразования из унарной кодировки в вышеупомянутую двоичную кодировку.Это можно сделать всего двумя символами, но детали действительно сложны, и я снова собираюсь их описать.Вы можете проработать детали, если хотите.
Надеюсь, это поможет!