1610906301-73dade1bb16d31c957842031de4c898c (Краткий конспект к экзамену), страница 5

Затем заменим команду F:=f(H1,...Hk) на последовательность команд:R1*:=H1R2*:=H2…Rk*:=HkPf*F:=R0*Теперь вновь перенумеруем команды полученной программы (исходной с добавленной частью)числом начиная с 0 и заменим во всей программе операторы вида if… goto m, goto m такимобразом:• Если m не было номером команды в исходной программе Р (т. е. Это номер команды,исходно не обозначенной (номер, останавливающий программу), то заменяем m на число,которое завершает программу.• Если эта команда внутри вставленного фрагмента и предназначена для выхода из него тозаменяем m на номер команды, следующей после этого фрагмента• Если эта команда — для перехода на другую команду, заменяем m на такое, чтобыкоманда переводила на ту же команду, что и раньше.Таким образом мы избавились от одной дополнительной команды (от остальных аналогично),получив программу, эквивалентную исходной, что и требовалосьДалее мы докажем что Классы функций, вычислимых на Мини-Машинах и частичнорекурсивных функций эквивалентны:Теорема 7.2 (О эквивалентности ЧРФ и функций, вычислимых на ММ)Функция частично рекурсивная <=> функция вычислима на ММ.Доказательство:=>Простейшие функции вычисляются следующим образом:0(x) => 0:R0=0s(x)0:inc R11:R0:=R1I(n,m)(x1...xn)0:R0:=RmОператоры:S (суперпозиция):Пусть h1(x1...xn)...hk(x1...xn), h(y1..yk) — вычислимы на ММТогда их композиция вычислима на РММ следующей программой:Ri:=xi, 1≤i≤n0:R(n+1):=h1(x1...xn)1:R(n+2):=h2(x1...xn)…k-1:R(n+k):=hk(x1...xn)k:R0:=g(R(n+1),...R(n+k))R (примитивная рекурсия):Пусть функции g(x1...xn), h(x1,...xn,y,f(y,x...xn)) вычислимы на ММ, тогда0:R0:=g(R1...Rn)1:R(n+2):=02:if R1=0 goto 73:R0:=h(R2,...R(n+1),R(n+2),R0)4:inc R(n+2)5:dec R16:goto 2μ (Оператор минимизации)Пусть g(x1...xn,y) вычислима на ММ, тогда0: R0:=01: R(n+2):=g(R1,…,Rn,R0)2: if R(n+2)=0 goto 53: inc R04: goto 1Таким образом ввиду определения ч.р.ф мы получили что любая ч.р.ф вычислима на ММ.<=Пусть Α — объект (регистр, команда и т. д.) γ(Α)∈Ν — его код.

Будем последовательнокодировать различные объекты, связанные с мини-машинами.Закодируем i - основной регистр так: γ(Ri)=iТеперь закодируем команды:γ(Ri=n)= <0,γ(Ri),n>γ(Ri=Rj)= <1,γ(Ri),γ(Rj)>γ(inc Ri)=<2,γ(Ri)>γ(dec Ri)=<3,γ(Ri)>γ(if F=0 goto m)=<4,γ(F),m>γ(goto m)=<5,m>Замечание: если регистр Q упомянут в команде C то γ(Q) ≤ γ(C)Можно заметить что множество всех кодов команд рекурсивно, так как x — код команды <=>seq(x) ^ ((lh(x)=2)^(x)0∈{2,3,5} v ((lh(x)=3) ^((x)0∈{0,1,4})), где 0..5 — нулевые координатыкоманд, закодированных вышеТеперь закодируем машины:Пусть Μ — машина, имеющая вид0:С01:С1…k-1: C(k-1), где Ci=i-ая командаТогда γ(M)=<γ(1),...γ(C(k-1))>Заметим что множество всех кодов машин также рекурсивно, поскольку x — код машины <=>seq(x) ^ (∀i< lh(x) ((x)i — код некоторой команды)) как конъюнкция координаты с ограниченнымквантором всеобщности и функции seq(x).Теперь закодируем состояния регистровЗаметим что если регистр Ri используется в программе то код Ri≤код команды ≤код программы,поэтому имеет смысл рассматривать только регистры номера которых ≤ кода программы.Определение 7.7Пусть а — номер некоторой ММ.

Конфигурация этой машины в некоторый момент времени —это <[ΚР], <R0,..[Ra]>>, где [KP] — содержимое командного регистра, а [Ri] - содержимое i-горегистра в этот момент времени.Код конфигурации: x=<[KP],<[R0],..[Rk]>>Теперь закодируем вычисление:Если в процессе завершившегося вычисления ММ находилась последовательно вконфигурациях с кодом C0..Ci, то кодом этого вычисления назовем <γ(C0),...γ(Ci)>Теперь мы введем отношение T(m,x,y), где m — код некоторой Мини-Машины, x — код<x1….xn>, а y — код вычисления, начатого в конфигурации ([KP], [R0],...[Rm]), где [R0]...[Rm]— начальный отрезок последовательности 0, (x)0, ...(x)(lh(x)-1),0,0…Предположим, что существуют о.р.ф КР(m,x,t) и Reg(m,x,t), такие что КР(m,x,t) — содержимоекомандного регистра, а а Reg(m,x,t) — подсостояния регистров <[R0],[R1]...[Rm]> миниМашины с кодом m при входных данных с кодом x после t шагов).Скажем, что m,x,y связаны отношением T, если1)m — код Мини-Машины (ранее было показано, что оно вычислимо)2) x и y — коды (последовательности и вычисления соответственно) (условие x — кодпоследовательности/вычисления вычислимо)3)∀i<lh(y) (((y)i=<KP(m,x,i),Reg(m,x,i)>))4)В последней конфигурации командный регистр не равен никакому номеру команды[*].

Этаoконфигурация имеет код y(lh(y)- 1, y=<y0...ym>. В этой конфигурации контрольный регистрooвычисляется как (y)lh(lh(y)- 1)0. Тогда условие [*] эквивалентно (((y)(lh(y)- 1))0 ≥lh(m))(Поскольку KP>lh(m), то ему некуда перейти, не завершив при этом программу) (Отношение,данное выше вычислимо)5)Во всех предыдущих конфигурациях [*] не выполняется.Это условие можно записать как ∀i<lh(y) [i+1≠lh(y) → ((y)i)0<lh(m)] (командный регистрменьше длины программы, ему есть куда переходить) (условие также вычислимо)Тогда заметим что T(m,x,y) является конъюнкцией перечисленных выше условий, вычислимостьчетырех из которых уже доказана. Доказав, что KP(m,x,t) и Reg(m,x,t) вычислимы мы докажемвычислимость третьего условия и как следствие всего отношения (конъюнкция вычислимыхотношений — вычислимое отношение).Определим их совместной рекурсией:KP(m,x,0)=...Reg(m,x,0)=…KP(m,x,t+1)=h0(m,x,t,KP(m,x,t),Reg(m,x,t))Reg(m,x,t+1)=h0(m,x,t,KP(m,x,t),Reg(m,x,t))Мы будем строить каждое значение с помощью разбора случаев (см.

Предложение 6.8), однакомы введем к исходным k функциям f(k+1)(x`), выполняющуюся при ¬(P1(x1)vP2(x`)...Pk(x`)) (тоесть выполняющуюся в случае, когда ни одно из перечисленных отношений не истинно).Если m — номер ММ, x- код последовательности данных, то код команды, которая будетисполняться - (m)_KP(m,x,t) — Будем далее обозначать это cm(m,x,t)Тогда заметим, что KP(m,x,0)=0 (Контрольный регистр на нулевом шаге равен 0)Заметим, что на KP(m,x,0) могут подействовать команды goto k и if F=0 goto k, при встречедругих команд он просто увеличивается на единицу. Также заметим что при встрече командыgoto k (cm(m,x,t))0=5 (нулевая координата равна 5), но тогда нам нужно приравнять значение КРк k, которое в свою очередь содержится в (cm(m,x,t))1.В случае же if F=0 goto k (тогда cm(m,x,t))0=4) нам нужно сделать то же самое, но при условии,что F равен 0, код регистра F содержится в ((cm(m,x,t))1, то есть его можно вызвать по командеReg(m,x,t)_(cm(m,x,t))1 (регистр с номером «код регистра F» и есть регистр F).

Тогда мы безтруда можем записать KP(m,x,t+1):KP(m,x,t+1)=• (cm(m,x,t))1, если (cm(m,x,t))0=5• (cm(m,x,t))2, если ((cm(m,x,t))0=4) ^ (Reg(m,x,t)_(cm(m,x,t))1=0• KP(m,x,t)+1 для остальных случаев.Теперь запишем аналогичным образом Reg(m,x,t)Reg(m,x,0) будет равняться коду последовательности из первых (m+1) элементовoпоследовательности 0,x(0),x(1)...(x)(lh(x)- 1, 0, 0….ТогдаoReg(m,x,0)=μ s[(seq(s))^(lh(s)=m+1)^((s)0=0)^(∀i<lh(s) (1≤i ^ i≤lh(x)) → (s)i=(x)(i- 1)) ^ ∀i<lh(s)(i>lh(x) → (s)1=0)]Заметим, что на значение Reg(m,x,t) могут поменять только 4 оператора:0)R:=k, (cm(m,x,t))0=01)R:=G, (cm(m,x,t))0=12)inc(R), (cm(m,x,t))0=23)dec(R), (cm(m,x,t))0=3Будем рассматривать случаи в соответствии с их нулевыми координатами:Случай 0)cm(m,x,t)=<0,γ(R),k>Напомним, что код последовательности имеет вид Pr0^([R0]+1)*Pr1^([R1]+1)...Prs^[R]+1….Где Pr — простые числа.

Тогда нам достаточно заменить степень [R]+1 на (cm(m,x,t))2+1 =k+1Таким образомReg(m,x,t+1)=[Reg(m,x,t)/P^(Reg(m,x,t)_(c(m,x,t))2+1)(cm(m,x,t))1]*P^((cm(m,x,t))2+1)_cm(m,x,t)1 (P в степени Reg(m,x,t)_(c(m,x,t))2+1 и с индексом(cm(m,x,t))1, то есть мы делим код текущего состояния регистра (произведения простых чисел)на простое число P(cm(m,x,t))2 (число с номером «код R») в степени [R]+1 и домножаем на этоже простое число в степени k.Таким образом мы закодировали один случайПо аналогии рассмотрим случай номер 1Там нам нужно будет заменить степень при числе с номером «Код R» на степень при числе сномером «код G», это можно сделать так:Reg(m,x,t+1)=[Reg(m,x,t)/P^Reg(m,x,t)_(c(m,x,t))2+1)*P^(Reg(m,x,t)_((cm(m,x,t))_2)+1)Случай номер 2 (inc) рассматривается гораздо проще: Нам всего лишь нужно увеличить наединицу степень при числе с номером «Код R»Это делается так: Reg(m,x,t+1)=Reg(m,x,t)*P_(cm(m,x,t))1Наконец в случае 3oReg(m,x,t+1)=Reg(m,x,t)/P^Reg(m,x,t)_(cm(m,x,t))1+1*P^(Reg(m,x,t)_(cm(m,x,t))+1)- 1(Все эти операции дают нам требуемые результаты, поскольку меняя степень простого числа мыполучаем другой код, соответствующий требуемой нам конфигурации).В остальных же случаях Reg(m,x,t+1)=Reg(m,x,t) (Значение не меняется)Таким образом мы показали и вычислимость Reg, что в свою очередь показывает нам, что иT(m,x,y) вычислимоТеперь вспомним, что если y — код его вычисления, то код последней его конфигурации имеетooвид (y)(lh(y)- 1), тогда ((y)(lh(y)- 1))1 — код состояния регистров в этой конфигурации, но тогдаoмы можем получить [R0] как (((y)(lh(y)- 1))1)0 Обозначим это значение как рекурсивнуюфункцию U(y).

Однако заметим тогда, что если функция f(x1...xn) вычисляется на некоторойММ, то у этой ММ есть номер, пусть он равен m. Но тогда результат работы ММ можнозаписать как U(μyT(m,(x1...xn),y)) — но это ч.р.ф., что и требовалось (эта функция вычисляетнулевой регистр минимального y, являющегося кодом вычисления ММ с номером m и входнымиданными x1...xn то есть y связанного с m и x.1..xn отношением T)Таким образом Теорема доказана.Теорема 7.3 (Об универсальной функции)1)Существует (k+1)-местная ч.р.ф ψ(m, x0...x(k-1)) такая что для любой ч.р.ф. f(x0...x(k-1))найдется m∈Ν, такая что f(x0...x(k+1))~ (эквивалентна) ψ(m,x0...x(k-1))2)О.р.ф, удовлетворяющей таким условиям не существуетДоказательство:1)Заметим, что ввиду того, что ч.р.ф эквивалентны функциям, вычислимым на мини-машинах,то можно заметить, что если f(x`) - чрф то f(x`)~ U(μy(T(m,x`,y)) для некоторого m, но в такомслучае можно поставить ψ(m,x`)=U(μy(T(m,x`,y)).2)Пусть такая о.р.ф ψ(m,x`) существует.