1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Если эта команда имеет вид INC i, то (e)ct(e,x,n) = 0, при этом0³´параметр i вычисляется следующим образом: i = (e)ct(e,x,n) . Если же эта команда1³´имеет вид DEC i, j, то (e)ct(e,x,n) = 1, и тогда параметры i, j можно вычислить0´³´³так: i = (e)ct(e,x,n) , j = (e)ct(e,x,n) . Наконец, проверка условия положительности12содержимого i-го регистра после n шагов вычислений равносильна проверке выпол´ > 0.нимости условия (rg(e, x, n))³(e)ct(e,x,n)1Далее, значение rg(e, x, n + 1) можно вычислить с помощью следующей неформальной схемы:< r0 , . . .

, ri + 1, . . . , re+k >, если Prog(e), Seq(x), команда сномером ct(e, x, n) имеет вид INC i,и rg(e, x, n) =< r0 , . . . , re+k >,¦< r0 , . . . , ri −1, . . . , re+k >,если Prog(e), Seq(x), команда сномером ct(e, x, n) имеет вид DEC i, j,rg(e, x, n) =< r0 , . .

. , re+k >, и ri > 0,rg(e, x, n + 1) = < r0 , . . . , ri , . . . , re+k >,если Prog(e), Seq(x), команда сномером ct(e, x, n) имеет вид DEC i, j,rg(e, x, n) =< r0 , . . . , re+k >, и ri = 0,< r0 , . . . , re+k >,если Prog(e), Seq(x), в программенет команды с номером ct(e, x, n),и rg(e, x, n) =< r0 , . .

. , re+k >,0во всех остальных случаях.Заметим, что в этой схеме можно объединить второй и третий случаи, поскольку¦если ri = 0, то ri −1 = ri .§ 13. Кодирование машин Шёнфилда53Введем вспомогательную примитивно рекурсивную функцию¸·x,β(i, x, y) = ex(i,x) · py+1ipiкоторая удовлетворяет условию: если x =< x0 , . . . , xi−1 , xi , xi+1 , . . . , xk > — код последовательности и i 6 k, то β(i, x, y) =< x0 , . . . , xi−1 , y, xi+1 , . . . , xk >.Тогда окончательно получаем следующую формальную схему для вычисленияrg(e, x, n + 1) = ³³´³´´´³β(e),rg(e,x,n),rg(e,x,n)+1, если Prog(e), Seq(x),ct(e,x,n)1(e)ct(e,x,n)1ct(e,³ x, n) < lh(e),´и(e)= 0,ct(e,x,n)0³³´³´´β (e)¦´−, rg(e, x, n), rg(e, x, n) ³1 , если Prog(e), Seq(x),ct(e,x,n)1(e)ct(e,x,n)=1ct(e,³ x, n) < lh(e),´и(e)= 1,ct(e,x,n)0rg(e, x, n),если Prog(e), Seq(x),и ct(e, x, n) > lh(e),0в остальных случаях.Таким образом, используя предложение 24, мы полностью выписали требуемуюсхему совместной рекурсии, в которой участвуют только примитивно рекурсивныефункции и отношения.

Следовательно, ct и rg — п.р.ф.Определение. Определим трехместный предикат:Stop(e, x, n) ⇐⇒ Выполняются следующие три условия:(a) e — код некоторой программы P,(б) x =< x1 , . . . , xk > — код некоторой последовательностинатуральных чисел,(в) программа P, начав работу с содержимыми регистров0, x1 , . . .

, xk , 0, 0, . . . , останавливается после n-го шага.Лемма 32. Предикат Stop(e, x, n) примитивно рекурсивен.Доказательство. Заметим, что если выполняются условия (а) и (б) из определениявыше, то предикат Stop(e, x, n) истиннен тогда и только тогда, когда машина Шёнфилда с кодом e не найдет команду для исполнения впервые только после n-го шага.Следовательно, имеет место эквивалентноть:¡¢¡¢Stop(e, x, n) ⇐⇒ Prog(e) & Seq(x) & ct(e, x, n) > lh(e) & ∀j < n ct(e, x, j) < lh(e) .Отсюда, используя леммы 27, 29, 31, заключаем, что отношение Stop(e, x, n) примитивно рекурсивно.54Глава III. Формализации понятия вычислимой функцииОпределение. Пусть натуральные числа e и x удовлетворяют следующим тремусловиям:a) e — код некоторой программы P ,б) x =< x1 , .

. . , xk > — код некоторой последовательности натуральных чисел,в) программа P , начав работу с содержимыми регистров 0, x1 , . . . , xk , 0, 0, . . . ,останавливается.Тогда кодом вычисления на машине Шёнфилда с номером e и начальными содержимыми регистров 0, x1 , . . . , xk , 0, 0, . . . будем называть код последовательности< rg(e, x, 0), . . . , rg(e, x, m) >, состоящей из всех последовательно записанных кодовсостояния регистров по ходу вычислений, причем считаем, что в последнем из этихсостояний произошла остановка машины.Если y — код вычисления, то результат этого вычисления содержится в 0-ом регистре после остановки и может быть вычислен с помощью примитивно рекурсивнойфункции³´U (y) = (y)lh(y)−¦ 10.Если для e, x ∈ ω хотя бы одно из условий (а), (б), (в) не выполнено, то кодвычисления не определен.Определение.

Пусть k ∈ ω, определим (k+2)-местный T -предикат Клини:Tk (e, x1 , . . . , xk , y) ⇐⇒ e — код некоторой программы, а y — кодвычисления по этой программе с начальнымисодержимыми регистров 0, x1 , . . . , xk , 0, 0, . . .Лемма 33. Предикат Tk (e, x1 , . . . , xk , y) примитивно рекурсивен.Доказательство. Для фиксированного k ∈ ω имеет место эквивалентность¦Tk (e, x1 , . . . , xk , y) ⇐⇒ Seq(y) & Stop(e, < x1 , . . .

, xk >, lh(y)−1) &³´∀i < lh(y) (y)i = rg(e, < x1 , . . . , xk >, i)(в правой части эквивалентности опущен конъюнктивный член Prog(e), посколькуон уже учтен в определении предиката Stop).Отсюда, в силу лемм 27, 31, 32, заключаем, что Tk — примитивно рекурсивныйпредикат.§ 14.Машины Шёнфилда vs Частично рекурсивныефункцииМы, наконец, готовы к тому, чтобы привести доказательство теоремы о частичнойрекурсивности функций, вычислимых на машинах Шёнфилда.Теорема 34.

Любая функция, вычислимая по Шёнфилду, является частично рекурсивной.§ 14. Машины Шёнфилда vs Частично рекурсивные функции55Доказательство. Пусть f (x1 , . . . , xk ) — произвольная частичная функция, вычислимая по Шёнфилду. Следовательно, существует программа P для машины, котораявычисляет f (x1 , . . .

, xk ). Пусть e — код программы P , а x1 , . . . , xk — произвольныезначения аргументов f .Если f (x1 , . . . , xk ) определено, то P на входных данных x1 , . . . , xk останавливается. Следовательно, определен код вычисления y на машине с программой P и сначальными содержимыми регистров 0, x1 , . . . , xk , 0, . .

. , причем U (y) = f (x1 , . . . , xk ).Другими словами, существует y такой, что предикат Tk (e, x1 , . . . , xk , y) истиннен. Заметим, что тогда данный y является единственным со свойством Tk (e, x1 , . . . , xk , y),а значит, он является наименьшим с такими свойствами. Отсюда заключаем, чтоf (x1 , . . . , xk ) = U (µy[Tk (e, x1 , . . . , xk , y)]).Если же f (x1 , . . . , xk ) не определено, то P на входных данных x1 , . .

. , xk никогдане остановится. Следовательно, не существует кода вычисления y на машине P сначальными содержимыми регистров 0, x1 , . . . , xk , 0, . . . Следовательно, для любогоy предикат Tk (e, x1 , . . . , xk , y) ложен, и значит значение U (µy[Tk (e, x1 , . . . , xk , y)]) тоже не определено. Таким образом, опять выполняется соотношение f (x1 , . . . , xk ) =U (µy[Tk (e, x1 , . . . , xk , y)]).Так как Tk — примитивно рекурсивный предикат, то µy[Tk (e, x1 , . . . , xk , y)] — частично рекурсивная функция. Поскольку U — примитивно рекурсивная функция, тофункция f (x1 , . . . , xk ) = U (µy[Tk (e, x1 , . .

. , xk , y)]) частично рекурсивна.Из теоремы 34 можно вывести несколько важных следствий. Следующие четыре результата безусловно можно считать достаточным оправданием той трудоемкойработы, которую мы проделали в двух предыдущих параграфах.Следствие 35. Частичная функция вычислима на машине Шёнфилда тогда итолько тогда, когда она является частично рекурсивной.Доказательство. Следует из теоремы 16 и теоремы 34.Теорема 36 (теорема Клини о нормальной форме).

Для любой k-местной частичнорекурсивной функции f (x1 , . . . , xk ) существует натуральное число e такое, чтоf (x1 , . . . , xk ) = U (µy[Tk (e, x1 , . . . , xk , y)]).Доказательство. Поскольку f (x1 , . . . , xk ) частично рекурсивна, то она вычислимапо Шёнфилду. Следовательно, найдется e — код программы, которая вычисляетфункцию f (x1 , . . .

, xk ). Из доказательства теоремы 34 следует, что e — искомое.Следствие 37. Любая ч.р.ф. может быть получена из простейших функций спомощью конечной последовательности применений операторов S, R или M , в которой общее число применений оператора M не превосходит 1.Доказательство. Функция U и предикат Tk примитивно рекурсивны и, следовательно, могут быть получены из простейших функций только c помощью операторов Sи R. Таким образом, доказываемое утверждение следует из теоремы Клини о нормальной форме.Определение.

Пусть k ∈ ω, K — некоторое семейство k-местных частичных функций. (k+1)-местная частичная функция F (x0 , x1 , . . . , xk ) называется универсальнойдля семейства K, если выполняются следующие условия:1) для любого n ∈ ω существует f ∈ K такая, что F (n, x1 , . . .

, xk ) = f (x1 , . . . , xk );2) для любой f ∈ K существует n ∈ ω такое, что F (n, x1 , . . . , xk ) = f (x1 , . . . , xk ).Другими словами, K совпадает с множеством функций {F (0, x), F (1, x), F (2, x), . . .}.56Глава III. Формализации понятия вычислимой функцииТеорема 38 (об универсальной ч.р.ф.). Существует (k+1)-местная ч.р.ф. F (x0 , x1 ,. . . , xk ), универсальная для семейства всех k-местных ч.р.ф.Доказательство. В качестве F можно взять (k+1)-местную частично рекурсивнуюфункциюF (x0 , x1 , . . . , xk ) = U (µy[Tk (x0 , x1 , . . .

, xk , y)]).Из теоремы Клини о нормальной форме следует, что F — универсальная для всехk-местных частично рекурсивных функций.Из теоремы об универсальной ч.р.ф. следует, что существует универсальная машина Шёнфилда Puniv , которая в определенном смысле способна заменить бесконечное семейство всех машин Шёнфилда. Работу Puniv можно описать следующим образом (см. рисунок): на вход универсальной машины подается кортеж данных (e, x);универсальная машина по коду e конструирует программу Pe , соответствующую этому коду, и запускает ее на входных данных x; результат f (x) работы программыPe выдается на выход Puniv и является окончательным результатом ее работы, т. е.F (e, x) = f (x).(e, x)вход -Punivвыход-F (e, x)6f (x)x?P0P1...Pe...Pn...Определение. Пусть k ∈ ω.

Для каждого e ∈ ω введем обозначениеæke (x1 , . . . , xk ) = U (µy[Tk (e, x1 , . . . , xk , y)]).Функцию æke (x1 , . . . , xk ) будем называть k-местной частично вычислимой функциейс клиниевским номером e. В случае одноместных функций будем просто писать æe (x)без верхнего индекса.Замечание. Если e — номер машины Шёнфилда, которая вычисляет функцию f ,то e также будет клиниевским номером этой функции.

Но обратное, вообще говоря,неверно! Не любой клиниевский номер функции является номером машины Шёнфилда, вычисляющей эту функцию. Более того, если e — клиниевский номер, неявляющийся номером машины, то предикат Tk (e, x, y) тождественно ложен, и значитфункция æke (x) нигде не определена.Следствие 39.

Характеристики

Список файлов лекций