Какие операции выполняет машина Тьюринга при обработке одного символа на ленте?

На каждом шаге выполняются элементарные операции:

- чтение символа из ячейки ленты;

- запись символа на ленту;

- перемещение головки на один шаг влево или вправо.

Для начала работы машины Тьюринга на ленте должна быть записана информация, которая подлежит преобразованию в процессе решения задачи. Головка должна быть установлена над первым обрабатываемым символом. Машина должна находиться в начальном состоянии.

Работа машины Тьюринга происходит по шагам. На каждом шаге выполняются следующие действия:

· С ленты считывается символ Xt, находящийся под головкой.

· В соответствии с алгоритмом решения задачи в зависимости от текущего состояния машины Qt и считанного символа Xt блок управления формирует новый символ Yt , который записывается на ленту вместо символа Xt.

· В соответствии с алгоритмом решения задачи блок управления формирует сигнал Yd , который поступает на привод перемещения головки и вызывает перемещение головки.

· В соответствии с алгоритмом решения задачи блок управления формирует код нового состояния Qt+1 и записывает его во внутреннюю память машины.

Далее последовательность действий повторяется. При этом возможны два случая.

В первом случае после определенного количества шагов машина переходит в конечное состояние. Это означает, что решение задачи закончено, и результат ее решения записан на ленте.

Во втором случае машина не переходит в конечное состояние, и работа машины происходит бесконечно. Это означает, что алгоритма решения данной задачи не существует (или что алгоритм решения задачи сформулирован некорректно).

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

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