Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Ых, У, А(х, у), ..., Л(яг, р))) =
?= jth (-ф. у, л (/(я, г/))....М/(я, */)))> ?**
ФД1, У. (/(?*, г/)), *.(/(*, г/)))) = ЧЧд:. Z/; /(г. уУУ,
где
I/» у, h(z), ..., f.'(z))\ ...
фДж, у, ti(z), ..., A(z)))'.
Значит, f(x, у) может быть получеиа при помощи примитивной рекурсии ИЗ Я,(ф!, ф*) И "Ф, т. е. f[xt у)&
Далее,
А (я, y)^U{j{x, у)), А (я, y)=tt{f(x, г/)), поэтому А (г. 1/), ? А(ж, 1/)&^пр.
Докажем теперь теорему о представлении вычислимой функции (а значит и произвольной частично-рекурсивной функции) через примитивно-рекурсивные функции в специальной форме (аналог теоремы Клини).
Теорема 5. Для всякой вычислимой функции f(xu хп) существуют такие примитивно-рекурсивные функции Fj{x 1, ..ял, у) и Gf{xu ..хп, у), что
/(**?1) ? ? *1 ^я) ^ 1 (^1> ? * Ч ^"1 * * ч УУ^О))1
Доказательство. Пусть /(#,, ..?„)—произвольная вычислимая функция, которую мы будем записывать короче как f{x), где x = (^!, ..., а:„). Рассмотрим машину Тьюринга, вычисляющую ее правильным образом. Пусть Т — программа машины и ки ..хг — состояния машины. Введем новое состояние х0 (символ х0 отличен от ки ..., хг) и дополним программу Т, заполнив все ее пустые клетки, а также клетки присоединенного столбца х0 следующим образом: если пустая клетка принадлежит строке а, то в нее помещается команда aSx0. Полученную программу обозначим через Т'. Если уело-
166 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
виться, что машина, соответствующая Т’ (которая фактически работает так же, как исходная), останавливается, попадая в состояние х0, то она будет вычислять функцию / так же, как исходная машина с программой Т. х Для машины Т' рассмотрим
У ^ * в момент времени t ее ленту
Ш и отметим на ней рабочую зо-
4------т-> ' ну. т. е, совокупность всех яче-
ра$очия зона J1 J
ек лепты, состоящую из ячеек, Рис- И в которых побывала головка
машины, и ячеек, в которых записан исходный основной код для х. По отношению к ячейке, которую в момент t обозревает головка, рабочая зона разбивается на две части 3( и 0tt — левую и правую части (см. рис. И). Кусок 3t расположен левее ячейки, обозреваемой головкой в момент t, — содержит
остальные ячейки рабочей зоны. Обозначим через Д — натуральное число, запись которого в двоичном счислении находится в ячейках 3г, и через Д— натуральное число, запись которого в двоичном счислении находится в ячейках если ее читать справа налево (инверсным образом). Очевидно, что
U BSB Д (а- . t) 1 /а = Д (х , t),
где х' — натуральное число, запись которого в двоичном счислении совпадает с записью исходного кода х, читаемого справа налево.
Пусть fs(x', f) —номер состояния в момент времени t, если в начальный момент запись на ленте характеризуется натуральным числом х'.
В момент времени t = О будет 3t =* А (пусто), совпадает с множеством ячеек, занятых записью основного кода. Поэтому
Д(г', 0) = х\
Ш, 0) = 0,
Ых\ 0)= 1.
С другой стороны, очевидно,
Д(ж', ? + 1) = чД(Д(х1, t), fz{x\ t), U{x\ t)), fi(x'i t+ l) = tys(fi(x', t), f2(x', t), fs(x\ t)), fz{x\ t+ l)_=iMA(*'. i), U{x\ t), U{x\ *)).
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
167
В самом деле, зная в момент времени ? числа и(х\ ?), О» 1ЛХ\ ?)> мы находим число, обозреваемое головкой в момепт времени ?,— это будет младший разряд в двоичной записи /, (х', ?) и состояние машины, номер которого есть /э(я', 0- Эти две величины позволяют по таблице Т' найти новое значение этой ячейки, новое состояние (номер состояния) и характер движения и, в конечном счете, числа А(ж’» (4*1), /а(л4, ?4*1), ?4-1).
Эти преобразования и дают формулы для и фз.
Сейчас мы найдем их явное выражение. Для этого обозначим через Г, (г 1, г2), Т2{ги z2) и Т3(ги zz) соответственно функции, определяемые таблицей и дающие по входному символу и номеру состояния соответственно новый символ, номер нового состояния и номер движения (2 — для движения Ь, 1 — для движения 5 и 0 — для движения Д). Для осталышх значений из расширенного натурального ряда полагаем значения этих функций равными 0. Очевидно, что Ти Т2, так как они в ко-
нечном числе точек принимают ненулевые аначения.
Обозначим через %(г) *) младший разряд г и для сокращения записи положим '
А = А {х\ ?) ,
и=и{х\ о,
/3^/э(а4, ?),
7 = Г|(х(/|), А),
а = т3(х(и), А).
Тогда при любом с1 = 0, 1, 2
/.(*', *+1)-Г,(х(Л)', /з).
Соответствующие равенства для ? + 1) и
/8(ж', ?4*1) составим сначала отдельно для каждого случая:
а) й = 1 (движение 5)
и? + 1) = А " X (А) + А
/.{*', ?4-1) =/8;
*) Очевидно, ЧТО 1 (г) <= Рир.
55,0 п. 1. Ф^ШЦИийАЛЬйЫК 1ЖС1'ШЫ С ОПЕРАЦИЯМИ
б) й = 0 (движение Я)
1Л*\? + 4) ™[т]* /,(*', г + 1) -=2/а + у;
в) А — 2 (движение Ь)
Д (*А « + 1) = 2(/х ~ X (/1) + У) + X (/я)*
Вспоминая, что {1[х'л ? + 1), /г(^,1 ?+1) и Д(лА ? + 1) — это значения функций ф], ф2 и ф3, и объединяя соответствующие равенства из разных случаев, имеем
Ф1 (А> А. А) = (А — х (А)+ 771 (7 (А).* А)И +
+ [”] -8ё а + х (А) -Бв (л — I), Ф* (А* /я. /а) - (2А + Г1 (X (А), А)) -эёй +
+ A'Sgf7.Sg(^^~ 1) + [%] (сг — 1), ф3(А> А. А) = ТАуЛк), А)*
Отсюда вытекает, что ф1? ф2, фзеЯпг,.'
