Составители:
Рубрика:
q(t,x)= Q
∼
(t, 1, s(x), 0, n(x)).
Аналогично определим функции, задающие остальные элементы
четверки через t тактов:
∼
s(t,x)= S
(t, 1, s(x), 0, n(x)),
m(t,x)= M
∼
(t, 1, s(x), 0, n(x)),
n(t,x)= N
∼
(t, 1, s(x), 0, n(x)).
Функции q(t,x), s(t,x), m(t,x), n(t,x) рекурсивны, поскольку
получены суперпозицией рекурсивных функций.
Машина останавливается, когда приходит в заключительное
состояние q
. Поэтому момент остановки t
0 0
(x) можно найти, если он
определен, из условия, что q=0:
(x)=μ
t
t
(q(t,x)).
0
Если значение f(x) не определено, машина никогда не
останавливается и t
0
(x) имеет неопределенное значение.
Следовательно, функция t
(x) является частично-рекурсивной.
0
Если значение t
0
(x) определено, можно найти остальные
элементы четверки для заключительной конфигурации:
s (x)=s(t (x),x),
0 0
(x)=m(t (x),x),
m
0 0
(x)=n(t (x),x).
n
0 0
(x)=m(t
Полагаем, что m
0 0
(x),x)=0. Тогда заключительная
конфигурация может быть представлена четверкой <0, s(f(x)), 0,
n(f(x))>. Рассмотрим операции преобразования этой конфигурации к
символьному виду, а именно
......
3210
0
Λ
Λ
iiiis
ccccaq
,
где - представление значения функции f(x). Напомним,
что все арифметические операции выполняются в k-ичной системе
счисления. Поскольку в k-ичной записи n(f(x))= …i
...
3210
iiiis
cccca
i i i
3 2 1 0
, для
получения соответствующих цифр f(x), а именно ,
необходимо взять запись n(f(x)) в обратном порядке. Очевидно, что
......
3210
iiiis
cccca
162
Страницы
- « первая
- ‹ предыдущая
- …
- 76
- 77
- 78
- 79
- 80
- …
- следующая ›
- последняя »
