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

UptoLike

ВУЗ: 

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

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

Рубрика: 

104
Глава 7
МАШИНЫ ТЬЮРИНГА:
ПРОБЛЕМА ОСТАНОВКИ,
ЯЗЫКИ ТИПА 0
§ 7.1. Универсальная
машина Тьюринга
В этой главе мы покажем, что существует машина Тьюринга U, которая по
заданному
коду произвольной машины Тьюринга T и кодированию входной
цепочки x будет моделировать поведение машины T с входной цепочкой x.
Такая машина U называется универсальной машиной Тьюринга. Её можно
рассматривать как вычислительную машину общего назначения, которая
достаточно мощна для того, чтобы моделировать любую вычислительную
машину, включая саму себя.
Мы покажем также, что не существует алгоритма (т.е. машины Тьюринга,
которая останавливается на всех входных цепочках), который мог бы
определить, остановится ли когда-нибудь произвольная машина Тьюринга T с
произвольной цепочкой x на её входе. Этот отрицательный результат
интенсивно используется как аргумент для того, чтобы показать, что многие
проблемы, относящиеся к различным классам языков, рекурсивно (т. е.
алгоритмически) неразрешимы.
Будет также показано, что имеются рекурсивно перечислимые множества,
которые не являются рекурсивными. Другими словами, есть множества,
которые распознаются машинами Тьюринга, но не такими, которые останавли-
ваются для всех входных цепочках.
Наконец, будет доказана основная теорема об эквивалентности класса
языков типа 0 и множеств, распознаваемых машинами Тьюринга.
Покажем, что универсальная
машина Тьюринга существует путём
действительного её построения.
Прежде всего, мы должны условиться относительно кодирования машин
Тьюринга и кодирования их входных цепочек. Поскольку произвольная
машина Тьюринга T
1
может иметь любое число допустимых символов ленты,
мы предполагаем, что все они будут кодироваться при помощи символов 0 и 1.
Очевидно, что для каждой Tm T
1
существует Tm T
2
с ленточными символами 0
и 1 и одним дополнительным символом ленты B (пробел), которая принимает
точно те строки из множества {0, 1}
*
, которые являются кодами слов,
принимаемых машиной T
1
. Принимая это во внимание, достаточно спроекти-
ровать универсальную машину Тьюринга
для машин Тьюринга с одинаковыми
ленточными алфавитами {0, 1, B}.
Машина Тьюринга с тремя допустимыми ленточными символами может
быть полностью определена при помощи таблицы, подобной табл. 7.1.

Страницы