Что изменяется в машине Тьюринга при изменении алгоритма её работы?

Приведем также пример задачи, при решении которой приходится вводить вспомогательные символы, которых нет ни в алфавите исходных данных, ни в алфавите выходных символов.

Пусть на ленте записана последовательность единиц, ограниченная слева и справа символами А. Необходимо сохранить на ленте исходную информацию и записать на эту же ленту ее копию. Исходную информацию и копию разделить символом *.

Идея решения задачи сводится к тому, что вначале все единицы заменяются вспомогательными символами (символами 0), а вместо правого символа А записывается символ разделителя *. Далее каждый символ 0 последовательно заменяется на символ 1 с одновременной записью символа 1 на ленту справа от разделителя. Граф машины Тьюринга, решающей эту задачу, приведен на рисунке 1.5.

Как видно из графа, задача решается за несколько проходов головки по ленте. Таблица работы машины, соответствующая графу рисунка 1.5, имеет вид таблицы 1.4.

Рисунок 1.5

Дата добавления: 2015-07-26; просмотров: 205; Нарушение авторских прав

Мы поможем в написании ваших работ!