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

UptoLike

ВУЗ: 

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

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

Рубрика: 

< j
+ +
, [n mod k], [m/k], nk + s . >.
Выполнение команды q
j
a
s
→ a
s
+
Нq
j
+
, не меняющей положение
головки, не изменяет значения m′ и n′: s′= s
+
, m′=m, n′=n. Эта
команда преобразует конфигурацию (1) к виду < j
+
, s
+
, m, n >.
Введем числовую функцию D(j,s), характеризующую
перемещение головки для команды q
j
a
s
→ a
s
+
D q
j
+
:
0, если D=П,
D(j,s)= 1, если D=Л,
2, если D=Н.
Введем также функции Q(j,s)=j
+ +
и A(j,s)=s . Если функции
D(j,s), Q(j,s)=j
+ +
и A(j,s)=s частичные, доопределим их равными
нулю. Таким образом, функции D(j,s), Q(j,s)=j
+ +
и A(j,s)=s -
рекурсивные.
Введем, наконец, в рассмотрение рекурсивные числовые
функции, характеризующие перемещение головки:
sgn
(j,s)= D(j,s),
δ
П
sgn
δ
Л
(j,s)= ⏐D(j,s) - 1⏐,
sgn
(j,s)= ⏐D(j,s) - 2⏐. δ
Н
Функция δ
П
(j,s) принимает значение 1 только если D(j,s)=0, т.е.
D=П, в противном случае δ
(j,s)=0. Функция δ
П Л
(j,s) принимает
значение 1 только если D(j,s)=1, т.е. D=Л, в противном случае
δ
Л
(j,s)=0. Наконец, функция δ
Н
(j,s) принимает значение 1 только
если D(j,s)=2, т.е. D=Н, в противном случае δ
(j,s)=0.
Н
Теперь мы можем обобщить преобразование четверки <j,s,m,n>
командой q
j
a
s
→ q
j
+
a
s
+
D в виде числовых функций
j′= j′( j,s,m,n)=Q(j,s);
s′=s′( j,s,m,n)= δ
(j,s)[n mod k]+ δ
П Л
(j,s)[m mod k]+ δ (j,s)A(j,s);
Н
(j,s)(mk+A(j,s))+ δ
m′=m′( j,s,m,n)= δ
П Л
(j,s)[m/k]+ δ (j,s)m;
Н
(j,s)[n/k]+ δ
n′= n′( j,s,m,n)= δ
П Л
(j,s)(nk+A(j,s))+ δ (j,s)n.
Н
160

Страницы