Q_4i, выработанный этим же блоком в предыдущем такте. Из P-ячейки знак сдвига направляется в механизм сдвига.
Логический блок общается с внешней памятью посредством читаю- щей и записывающей головки (каретки), в которой вмонтированы один входной канал _1(для считывания)_2 и один входной канал _1(для записи) логического блока; головка на схеме изображена прямоугольником, установленным против "обозреваемой" ячейки. Функции управления теперь уже чрезвычайно упрощены и заключаются по существу лишь в обеспечении сдвига не более, чем на одну ячейку, в соответствии с поступившим P-знаком. Знак состояния можно было бы фактически по-
давать из Q-ячейки прямо в логический блок L, образуя так называ- емую линию обратной связи, по которой в блок L поступает знак Qi, выработанный в нем же в предыдущем такте.
_22.1. Функционирование машины Тьюринга
К началу работы на ленту машины Тьюринга подаются начальные сведения (начальная информация); работа машины складывается из следующих один за другим тактов, по ходу которых происходит пре- образование начальной информации в промежуточные информации (к концу каждого такта совокупность знаков, хранящихся на ленте, об- разует соответствующую промежуточную информацию). В качестве на- чальной информации на ленту можно подать любую конечную систему знаков внешнего алфавита (любое слово в этом алфавите), расстав- ленную произвольным образом по ячейкам. Однако в зависимости от того, какая была подана начальная информация D, возможны два слу- чая: а) после конечного числа тактов машина останавливается, пода- вая сигнал об остановке; при этом на ленте оказывается изображен- ной некоторая информация b. В таком случае говорят, что машина применима к начальной информации D и перерабатывает ее в резуль- тирующую информацию b; б) остановка и сигнал об остановке никогда не наступают. В та- ком случае говорят, что машина не применима к начальной информа- ции D.
Говорят, что машина решает некоторый класс задач_._3, если машина применима всегда к информации, изображающей в определенном коде условия любой отдельной задачи этого типа и перерабатывает ее в информацию, изображающую в том же коде решение этой задачи.
Работа машины Тьюринга протекает следующим образом. Перед ее запуском на ленту заносится начальная информация (последователь- ность из пяти палочек ¦). Свободную ячейку будем обозначать _3"пус- тым знаком_._3" - символом ^. В "поле зрения" машины устанавливается определенная начальная ячейка. Каретка обозревает вторую ¦ слева.
Начальное внешнее и внутреннее состояния ¦ Q1.
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦ ^ ¦ ^ ¦
-----------------------------------------
_
Q_41
_1.5
Выполним программу в пошаговом режиме по следующей функцио- нальной схеме:
_1.0
+----------------------------------------+
¦ ¦ Q1 ¦ Q2 ¦ Q3 ¦ Q4 ¦ Q5 ¦
+-----+------+------+------+------+------¦
¦ ^ ¦ ^ПQ4 ¦ ^ЛQ3 ¦ ^ПQ1 ¦ ^НQ5 ¦ ^НQ5 ¦
+-----+------+------+------+------+------¦
¦ ¦ ¦ aНQ2 ¦ bНQ1 ¦ ¦ПQ1 ¦ ¦ЛQ1 ¦ ¦НQ5 ¦
+-----+------+------+------+------+------¦
¦ a ¦ aЛQ1 ¦ aПQ2 ¦ ¦ЛQ3 ¦ ^ПQ4 ¦ aНQ5 ¦
+-----+------+------+------+------+------¦
¦ b ¦ bЛQ1 ¦ bПQ2 ¦ ^ЛQ3 ¦ ¦ПQ4 ¦ bНQ5 ¦
+----------------------------------------+
_1.5
Первый такт. Обозревается знак ¦ из начальной ячейки (сдвиг Н) при состоянии Q1. Результат: выходная тройка аНQ2, т.е. знак ¦ заменен на знак a, а в ячейки Р,Q послана на хранение до следую- щего такта очередная команда НQ2.
Второй такт. Обозревается знак _2a из той же ячейки (сдвиг Н) при состоянии Q2. Выходная тройка aПQ2, т.е. знак a оставляется без изменения с переходом к команде ПQ2.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.