Языки и трансляции. Мартыненко Б.К. - 111 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

110
Если машина T останавливается с этими конкретными данными, то машина
U, в точности воспроизведя все движения машины T, тоже останавливается, а в
области данных будет зафиксировано финальное содержание ленты машины T.
Когда машина T останавливается, машина U может сообщить, находится ли
машина T в принимающем состоянии или нет.
Если машина T не останавливается, то машина U тоже не останавливается,
т. е. не принимает.
Так универсальная машина Тьюринга моделирует действия произвольной
машины Тьюринга T с её данными, закодированными на ленте универсальной.
Детальное устройство универсальной машины Тьюринга, которую мы описали
неформально, дано в табл. 7.2 (см. стр. 106−108).
Отметим, что эта универсальная машина Тьюринга использует 12
ленточных символов, но может моделировать только машину Тьюринга с
двумя допустимыми символами ленты. Но можно построить эквивалентную
универсальную машину Тьюринга, которая будет использовать только два
допустимых символа ленты. Для этого каждый допустимый символ её ленты
надо закодировать блоком из четырех символов 0 или 1. Часть ленты
универсальной машины Тьюринга с данными моделируемой машины T будет
использовать четыре ячейки вместо одной непустой ячейки.
§ 7.2. Неразрешимость
проблемы остановки
Проблема остановки машины Тьюринга формулируется следующим
образом: дана машина Тьюринга в произвольной конфигурации со строкой
непустых ленточных символов конечной длины. Остановиться ли она в конце
концов?
Говорят, что эта проблема рекурсивно не разрешима в том смысле, что не
существует алгоритма, который для каждой Tm и каждой конфигурации
определял бы, остановится ли она когда-нибудь. Это совсем не значит, что мы не
можем определить, остановится ли конкретная Tm в конкретной конфигурации.
При описании универсальной машины Тьюринга мы имели кодирование
для любой Tm с ленточными символами 0, 1 и B. Кодированием была цепочка
из множества {0, 1, c, L, R}
*
. Мы можем перенумеровать все такие цепочки,
перечисляя их в порядке возрастания длины. Цепочки одинаковой длины
упорядочиваются в соответствии со значением строки по основанию 5.
Предполагается, что эти 5 символов играют роль целых 0, 1, 2, 3, 4 в каком-
нибудь порядке. Аналогичным образом цепочки из множества {0, 1}
*
могут быть
тоже упорядочены. Первыми цепочками являются ε, 0, 1, 00, 01, 10, 11, 000, 001, ... .
Таким образом, имеет смысл говорить об i-й цепочке в множестве {0, 1}
*
.
Если мы предположим, что каждая цепочка из множества {0, 1, c, L, R}
*
является машиной Тьюринга (некоторые цепочки будут образованы
неправильно — они рассматриваются как Tm без каких-нибудь движений), то
также имеет смысл говорить о j-й машине Тьюринга, т. е. о машине, представ-
ленной j-й цепочкой из множества {0, 1, c, L, R}
*
.

Страницы