Что входит в состав машины Тьюринга? Что такое состояние машины Тьюринга? Для чего используется лента машины Тьюринга?

Машина Тьюринга

Идея машины Тьюринга выдвинута английским математиком А.Тьюрингом в 1936 г. С точки зрения теории алгоритмов машина Тьюринга представляет собой средство для описания алгоритмов преобразования информации. Для понимания принципа ее работы машина Тьюринга представляется в виде следующего технического устройства, структура которого показана на рисунке 1.2.

Что входит в состав машины Тьюринга? Что такое состояние машины Тьюринга? Для чего используется лента машины Тьюринга?

Машина Тьюринга состоит из ленты, головки и блока управления. Лента является внешней памятью машины. Лента служит для записи на нее исходных данных и результатов решения задачи. Физические принципы записи данных на ленту и чтения их с ленты не имеют значения. Лента бесконечна в обе стороны. Лента состоит из отдельных ячеек. В каждую ячейку может быть записан один символ. Запись и чтение данных с ленты производится при помощи головки. Будем считать, что при чтении информация в ячейке стирается.

Головка служит для записи данных на ленту и чтения информации с ленты.

Головка может перемещаться по ленте. Перемещение головки может производиться на один шаг влево или вправо к соседней ячейке. Для перемещения головки используется специальный привод, не показанный на рисунке 1.2.

Блок управления обеспечивает взаимодействие всех частей машины. Он воспринимает символ, считанный с ленты, формирует новый символ, который записывается на ленту, а также управляет перемещением головки. Блок управления имеет внутреннюю память. Информация, записанная во внутренней памяти, представляет собой состояние машины. Состояние машины зависит от того, какая информация была считана с ленты до текущего момента времени. Состояние машины может изменяться после чтения и анализа очередного символа.

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

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