----------------------------
...¦ ¦ S_4i ¦ ¦ ¦ ...
----------------------------
_ <--- _1Управляющая головка
_1.5
Внутренние состояния. Машина Тьюринга имеет конечное множество внутренних состояний:
Q={Q_40,Q_41,Q_42,...,Q_4m}.
В каждый момент времени машина Тьюринга находится в одном из этих состояний. После выполнения одного такта работы машина Ть- юринга может изменить свое состояние и воспринимать ячейку в сле- дующий момент времени в новом состоянии. Если машина Тьюринга в какой-то момент времени попадает в состояние Q_40, то работа ее за- канчивается. Состояние _2Q_40 называется _2пассивным (или _2заключитель-
_2ным). Все остальные состояния машины называются _2активными, из них
_2Q_41_2 - начальное состояние (машина Тьюринга всегда начинает свою работу, находясь в этом состоянии).
Программа. Под программой, вообще говоря, понимается некоторая последовательность команд, реализующих алгоритм, для конкретного исполнителя, имеющего свою систему команд, с помощью которых и записывается данный алгоритм.
Для машины Тьюринга программа, реализующая некоторый алгоритм называется тьюринговой программой. Она может быть записана двумя способами в виде функциональной схемы или в виде последователь- ности команд. Обычно эти два понятия не различают и считают, что функциональная схема - это и есть тьюрингова программа.
Мы же различаем эти два понятия, поскольку при решении задач на машине Тьюринга мы будем пользоваться программной моделью, для которой программа записывается в виде последовательности команд.
Таким образом, под функциональной схемой понимаем схематичес- кую запись тьюринговой программы. А под тьюринговой программой понимаем список всех команд вида:
xq --> x'Pq' где x и q - название строки и столбца в функциональной схеме, а
x'Pq'- тройка, расположенная на их пересечении (см. пункты 1.3 и
2.1).
_21.3. Система команд
В машине Тьюринга система элементарных операций очень упроще- на: на каждом отдельном такте команда предписывает лишь замену единственного знака S_4i, хранящегося в обозреваемой ячейке, каким либо другим знаком S_4j. При i=j это означает, что если в обозрева- емой ячейки не изменяется; при j=1 это означает, что если в обоз- реваемой ячейке хранился какой-либо знак, то он гасится. Далее упрощение заключается в том, что при переходе от одного такта к непосредственно следующему такту адрес обозреваемой ячейки может изменяться не более, чем на одну единицу, т.е. обозревается со- седняя слева или соседняя справа ячейка, или же обозревается та же ячейка, что и в предыдущем такте. Идея этого упрощения заклю- чается в том,_4 что необходимое для процесса содержание какой-либо отдельной ячейки отыскивается путем постепенной проверки всех ячеек подряд до тех пор, пока не будет обнаружена нужная ячейка.
Это очень удлиняет процесс, но вместе с тем возникает удобство: в командах программы вместо произвольных адресов обозреваемых ячеек можно ограничиваться применением всего лишь трех стандартных ад- ресов, которые изображаются специальными знаками:
_1.2
_2П (Вправо) - обозревать соседнюю справа ячейку,
_2Л (Влево) - обозревать соседнюю слева ячейку,
_2Н (На_месте) - продолжать обозревать ту же ячейку, что и прежде.
_1.5
В том случае, когда необходимо закончить выполнение алгоритма применяют еще один адрес:
_2С (Стоп) - прекратить выполнение программы.
_21.4. Обработка числовой информации в машине Тьюринга
В машине Тьюринга обработка информации происходит в логическом блоке, который также может пребывать в одном из конечного числа состояний. Пусть Q_41,Q_42,Q_43,...,Q_4m - специальные знаки, введенные для обозначений этих состояний.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.