Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

aqbp *, где a,bÎD;  p,qÎQ;  *Î{Л, П, Н},

здесь   a- символ , соответствующий строке таблицы;

q - столбцу таблицы.

На рисунке 4.1. показана линейная запись функциональной схемы для U1(n).

0qo1qsЛ	1qo2qsЛ	2qo3qsЛ	………	7qo8qsЛ	8qo9qsЛ	9qo0qoЛ	Lqo!Л®
®0qs0qsЛ	1qs1qsЛ	2qs2qsЛ	………	7qs7qsЛ	8qs8qsЛ	9qs9qsЛ	LqsL!Н

Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U1(n).

Такое представление программы обеспечивает взаимнооднозначное соответствие с табличной формой записи, а стало быть ничего из таблицы при этом не теряется и ничего не добавляется.

Как задать на ленте конфигурацию имитируемой машины? Напомним, что под конфигурацией Машины Тьюринга мы понимаем слово на ленте и положение каретки по отношению к слову. Здесь основная трудность: где записывать символ текущего состояния каретки.

Будем записывать символы исходного слова на ленте через ячейку. В образовавшиеся пустые ячейки ленты будем записывать справа от обозреваемого символа текущее состояние каретки.

Теперь рассмотрим проблему алфавита. Напомним, эта проблема состоит в том, что УМТ должна иметь определенный алфавит, который не может изменяться. В то же время мы не можем знать заранее, с какими алфавитами будут работать МТ, которые будет интерпретировать наша УМТ. Решение этой проблемы - кодирование символов из алфавита МТ символами алфавита УМТ. При этом важно позаботиться о том, чтобы:

Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, контрольные работы по алгебре.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки