Блок имеет два входных канала; по одному из них на каждой ста- дии работы машины (в каждом такте) поступает знак из обозреваемой ячейки, по другому - знак Q_4i того состояния, которое содержится в логическом блоке на данном такте; по выходному же каналу блок по- сылает в обозреваемую ячейку соответствующий, "переработанный" знак S_4j, являющийся однозначной функцией от сигналов S_4j, Q_4l, по- данных на вход. Команды, обусловливающие срабатывание машины на каждом отдельном такте, имеют вид:
ПQl, ЛQl, НQl, (l=1,2,3,...m), где первый знак заменяет адрес обозреваемой ячейки, а второй предписывает логическому блоку надлежащее состояние.
Знаки П,Л,Н,Q_41,Q_42,Q_43,...,Q_4m образуют внутренний алфавит машины.
Специфической особенностью машины Тьюринга является то, что на логический блок возлагается также и выработка на каждом данном такте той команды, которая будет подаваться в блок управления к началу следующего такта. Таким образом, логический блок имеет кроме канала для выдачи знака S_4j, еще два канала для выдачи двух знаков очередной команды.
Покажем это на следующей схеме:
_1.0
I Q_41
+----+---+----+
¦ _3Логический _4 ¦
¦ _3 блок ¦
+--+---+---+--+
a H Q_42
_1.3 где: I - знак обозреваемой ячейки;
Q_41 - знак состояния машины Тьюринга, которое содержится в логическом блоке на данном такте;
a - знак внешнего алфавита;
H - адрес следующей ячейки памяти машины Тьюринга;
Q_42 - знак состояния.
_1.5
При этом существенным является то, что входная тройка знаков
S_4j,P,Q_4l зависит исключительно от того, какая _1входная пара_1 знаков
S_4i, Q_4n была подана в том же такте на входы блока. Это означает, что логический блок реализует функцию, сопоставляющую каждой паре знаков S_4i,Q_4n тройку знаков S_4j,P,Q_4l. Эту функцию мы будем называть логической функцией машины, которую удобно изображать в виде пря- моугольной таблицы, столбцы которой занумерованы знаками состоя- ний, а строки - знаками внешнего алфавита; в каждой же ячейке таблицы записана выходная тройка знаков. Эту таблицу будем назы- вать функциональной схемой машины.
Например:
_1.0
+-----------------+
¦ ¦ Q_41 ¦ Q_42 ¦
+---+------+------¦
¦ I ¦ aНQ2 ¦ ¦
+---+------+------¦
¦ a ¦ ¦ ¦
+-----------------+
_1.5
Из вышеизложенного ясно, что работа машины Тьюринга вполне оп- ределяется той логической функцией, которую реализует логический
блок. Иными словами, две машины Тьюринга, работающие по одной функциональной схеме неразличимы, коль скоро мы интересуемся лишь тем, как они работают.
_2§2. Структурная схема машины Тьюринга
Структуру машины Тьюринга, состав отдельных ее блоков и их взаимодействие можно задать в виде структурной схемы, общей для всех машин Тьюринга.
_1.0
---------------------------------
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
---------------------------------
__ Q_41
¦+->+ +---<---+ +-->
¦ ¦ ¦ ¦ ¦
¦ +-------+ +-----+ +-----+
¦ ¦ L ¦ ¦ Q ¦ ¦ P ¦
a¦ +-------+ +-----+ +-----+
¦ ¦ ¦ ¦ Q_42 ¦ ¦
¦ ¦ ¦ +--->---+ ¦
+-<-+ +---------->-------+
_1.5
В этой схеме отражено разделение памяти на внешнюю и внутрен- нюю. Внешняя память изображена ячейками бесконечной ленты, пред- назначенными для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память - двумя ячейками для хране- ния очередной команды: Q-ячейка_2 хранит знак состояния и P-ячейка
- знак сдвига. В этих двух ячейках происходит задержка знаков P и
Q_4i, полученных на выходе логического блока L в данном такте рабо- ты, до начала следующего такта. Из Q-ячейки по так называемой ли- нии обратной связи в логический блок L поступает знак состояния
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.