Математическая логика и теория алгоритмов. Анкудинов Г.И - 75 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

Конфигурацию машины Тьюринга представим четверкой <j,s,m,n>,
где j – k-ичная запись номера состояния, а <s,m,n> - содержимое
ленты.
Рассмотрим три варианта команд: с перемещением головки
вправо, влево и с неподвижной головкой.
Выполнение команды q
j
a
s
→ a
s
+
Пq
j
+
преобразует конфигурацию
(4.1) к виду
…Λb
3
b
2
b
1
b
0
a
s
+
q
j
+
(4.2)
c c c c Λ… .
0 1 2 3
Значения j,s,m,n для конфигурации (2) обозначим через j′,s′,m′,n′.
Введем обозначения:
+
s
- номер замещающего символа a
s
+
;
j
+
- номер нового состояния головки q
j
+
;
[n mod k] – значение n по модулю k;
[n/k] – результат деления n на k нацело.
Тогда можно записать:
s′=[n mod k], поскольку головка обозревает младшую цифру n;
+
m′=mk + s
, поскольку сдвиг m влево относительно головки
равносилен умножению на k;
n′=[n/k].
Таким образом, четверка <j,s,m,n> преобразуется командой,
перемещающей головку направо, к виду < j
+ +
, [n mod k], mk+s ,
[n/k]>. Предполагаем здесь и далее, что все арифметические
операции выполняются в k-ичной системе счисления.
Выполнение команды q
j
a
s
→ a
s
+
Лq
j
+
преобразует конфигурацию
(4.1) к виду
…Λb
3
b
2
b
1
b
0
q
j
+
a
s
+
(4.3)
c c c c Λ… .
0 1 2 3
Для рассматриваемой команды можно записать:
s′=[n mod k],
m′=[m/k],
+
.
n′=nk + s
Таким образом, четверка <j,s,m,n> преобразуется командой,
перемещающей головку влево, к виду
159

Страницы