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

Тогда P v Q, P ^ Q, ¬P, P → Q такжерекурсивные.Доказательство:Пусть χP, χQ — характеристические функции P и Q соответственно. Тогда докажем для каждойоперации:Для ^:заметим что χP^Q=χP * χQ. (Произведение рекурсивных функций — рекурсивная функция).Для v:oχPvQ=χP(x`)+χQ(x`)- χP(x`)*χQ(x`)Для ¬:χ¬P=!sg(χP(x`))Для →:Заметим что P → Q<=> ¬P v Q. Но так как из предыдущих утверждений и по условию все частиэтого отношения рекурсивны, то и само отношения рекурсивна .Что и требовалось.Предложение 6.3Следующие отношения вычислимы:=, ≠, <,>,≤,≥Доказательство:Вновь докажем для каждого отношения:=:= можно представить как !sg(|x-y|) (суперпозицию рекурсивных функций.)≠:≠ можно в свою очередь представить как ¬(x=y), что по ранее доказанному предложениюявляется рекурсивным отношением.<:имеем отношение <(x,y)oЭто отношение можно представить как sg(y- x)Так как если x>=y то в результате имеем 0 и 1 в противном случае.≤:Представим как (x=y) v (x<y) (дизъюнкция рекурсивных отношений)>:oПредставить можно как sg(x- y)≥:Представить как (x=y) v (x>y) (дизъюнкция рекурсивных отношений).Таким образом утверждение доказано.Предложение 6.4Пусть g(i,x`) - о.р.ф.Тогда f(n,x)=Σ(g(i,x`) from i=0, to n) и h(n,x)= Π(g(i,x`) from i=0 to n) — о.р.ф.Доказательство:f(0,x`)=g(0,x`)f(n+1,x`)=sum(g(i,x`)+g(n+1,x`)=f(n,x`)+g(n+1,x`)h(0,x`)=g(0,x`)h(n+1,x`)=h(n,x`)*g(n+1,x`) (по аналогии).Предложение 6.5 (вычислимость отношений с ограниченными кванторами)Пусть P(i,x`) - вычислимое отношение.

Тогда вычислимы и отношения (∃i≤n)(P(i,x`)),(∀i≤n)(P(i,x)), (∃i<n)(P(i,x`)), (∀i<n)(P(i,x)).Доказательство:Заметим что существование можно представить как знак суммы элементов характеристическойфункции (поскольку он равен 0 если такого элемента нет и равен 1 при хотя бы одном элементе,удовлетворяющем условию P(x`). Таким образом (∃i≤n)(P(i,x`))=sg(ΣχP(i,x`) i=0 to n)Случай же с квантором всеобщности можно рассмотреть как произведение элементовхарактеристической функции, (ΠχP(i,x`) i=0 to n) а можно как отрицание существования (¬∃i≤n)(¬P(i,x`))Строгие знаки же можно выразить через уже построенные нестрогие условия и дополнительноеусловие что i≠n ((∃i≤n)(P(i,x`))^(i≠n))Аналогично для квантора существования (¬∃i<n)(¬P(i,x`))Утверждение доказано.На самом деле оператор минимизации можно использовать не только для отношения f(y,x`)=0,но и для любого другого вычислимого отношения. Докажем это:Предложение 6.6Если P(y,x`) - вычислимое отношение, то f(x`)=μ y (P(y,x`)) - ч.р.ф.Доказательство:Т.к.

P — вычислимо, то вычислима и его характеристическая функция. Тогда f(x`)=μ y (|χP(y,x`)1|=0) — ч.р.ф (т. к. ранее доказано, что |x-y| - ч.р.ф) ищущая наименьший y: (y,x`)∈P идействующая как оператор минимизации. Представив пример, мы доказали предложение.Пользуясь доказанным добавим в наш арсенал несколько новых вычислимых отношенийПредложение 6.7Следующие отношения вычислимы:1)x|y (x делит y)2)[x/y] (целая часть от деления x на y, при y≠0) (доопределим как x, если y=0)3)Prime(x) (является ли x простым)Доказательство:1)x|y <=> ∃t≤y:(x*t=y) (все отношения, перечисленные в эквивалентности вычислимы по ранеедоказанному.)2)[x/y]=μ z(((z+1)y>x)v(z=x))) (второй элемент дизъюнкции на случай y=0, поскольку в такомслучае первая часть не даст ответа).3)Prime(x) <=> (x>1) ^ (∀y≤x(y|x → (y=x) v (y=1)) (иными словами x>1 и если y делит x то y=xили y=1)Определим Pri: i-ое простое число (Pr0=2,Pr1=3,Pr2=5).

Pri можно задать примитивнойрекурсией:Pr0=2Pr(i+1)=μ y(y>Pri ^ Prime(y)) (наименьшее простое, большее Pi)Теперь зададим отношение ex(i,x): показатель при Pri в разложении x на простые множители.Докажем вычислимость данного отношения, определив (ex(i,0)=0)ex(i,x)=μ t((¬Pri^(t+1)|x) v (x=0)) (наименьшее t такое что pri^t+1 делит x, Либо 0 длядополнительного случая)Предложение 6.8 (Определение разбором случаев)Пусть P1(x`), P2(x`),…, Pk(x`) - вычислимые отношения, такие что для любого x` истинно вточности одно из них и f1(x`),f2(x`),…,fk(x`) - о.р.ф.Тогда g(x`)=f1(x`) если P1(x`), f2(x`) если Р2(x`)..., fk(x`) если Рk(x`) Также о.р.фДоказательство:Можно представить g(x`)=f1(x`)*χP1(x`)+...+fk(x`)*χPk(x`).

Так как для любого x` единице равнатолько одна характеристическая функция χPi(x`), значит что g(x`)=fi(x`), но поскольку каждая f— о.р.ф. то и g(x`) - о.р.ф.Введем также определение совместной рекурсии и перед ним сделаем уточнение пусть<k1,k2,...ki> последовательность тогда <k0,k1...k(i-1)>j - j элемент этой последовательности.Предложение 6.9 (Совместная рекурсия)Пусть g0(x`), g1(x`), h0(z0,z1,y,x`),h1(z0,z1,y,x`) - ч.р.ф. Тогда функции f0(y,x`),f1(y,x`),задаваемые так называемой таблицей совместной рекурсииf0(0,x`)=g0(x`)f1(0,x`)=g1(x`)f0(y+1,x`)=h0(x`,y, f0(y,x`), f1(y,x`))f1(y+1,x`)=h1(x`,y, f0(y,x`), f1(y,x`))Также частично рекурсивныеДоказательство:Обозначим F(y,x`)=<f0(y,x`),f1(y,x`)>Тогда если мы докажем ее вычислимость, то из этого будет следовать и вычислимость исходныхфункций (поскольку они являются композицией вычислимых функций F(y,x`) и координаты(дана ниже)F(0,x`)=<g0(x`),g1(x`)>F(y+1,x`)=<h0(x`,y, F(y,x`)0,F(y,x`)1),h1(x`,y, F(y,x`)0,F(y,x`)1)>Таким образом рекурсивность F(y,x`) доказана.Кодирование последовательностейБудем называть кодом последовательности натуральных чисел <x0,x1...x(k-1)> числоPr0^(x0+1)*Pr1^(x1+1)*...*Pr(k-1)^(x(k-1)+1) (Мы прибавляем к степеням единицу, так как еслиэтого не сделать, то например 1=Pr0^0=Pr0^0*Pr1^0….=<0,>=<0,0> (т. е.

Одним кодомкодируются разные последовательности).Введем функцию длины последовательности по ее коду, где x — код последовательности.lh(x)=μ k(¬(Prk|x)v(x=0))Также можно найти i элемент последовательности по ее коду, а именно с помощью функции exЗаметим что ex(i,x)=xi+1 тогда xi=ex(i,x)-1 (именно этим мы пользуемся в предложении 6.9, этуфункцию можно назвать i-ой координатой (но лучше не надо))Также покажем рекурсивность seq(x) — функции, показывающей, является ли x кодомпоследовательностиseq(x)<=>∀i ∀j<i (Pri|x → Prj(x))^(x≠0)Однако квантор i не ограничен, поэтому из полученного равенства не следует рекурсивностьseq(x).

Заметим тогда что x=a*Pri>Pri>i. Докажем последнее неравенство индукцией по ii=00<2Тогда заметим что i+1≤Pi<P(i+1) по построению функции Pi.Таким образом i можно ограничить x и формула имеет вид ∀i ≤x ∀j<i (Pri|x → Prj(x))^(x≠0), этаформула и доказывает рекурсивность требуемого отношенияТема 7:Мини-МашиныМини-машины (далее иногда ММ) — еще один способ формализации понятия вычислимости:Определение 7.1Каждая ММ имеет:Бесконечное число основных регистров R0, R1….Командный регистр (КР), в котором содержится номер выполняемой команды.И программа, в виде:0: команда1: команда…Определение 7.2 (Виды команд)Команды можно разбить на 3 больших типа:1)Команды присваивания:• H:=m (H — основной регистр, m∈N)• H:=G (H, G — основные регистры)2)Арифметические команды• inc(H) (H:=H+1)o• dec(H) (H:=H- 1)3)Команды перехода• goto m (переход в команду с номером m)• if F=0 goto m (F — основной регистр)Определение 7.3 (Процесс работы ММ)nС каждой Мини машиной P и каждым n∈N связываем n-арную функцию А P , котораявычисляется так: заносим x1...xn в соответствующие регистры R1...Rn, в остальные заносим 0 (втом числе и в КР, так ка первой на выполнение идет 0-ая команда.)Запускаем P; Если она остановится, то результат берем из R0, если же она никогда неnостановится, то А P (x1,..xn) — не определена.Определение 7.4nфункция f(x1...xn) называется вычислимой на P если f(x1,...xn) =А P (x1,..xn).Пример (вычисление x+y)0:R0=R1 (приравниваем R0 к x)1:if R2 =0 goto 5 (если нечего прибавлять, выходим из программы: попадание в команду, вкоторой ничего не записано — остановка машины)2:dec R2 («забираем» единицу из R2 (y)3: inc R0(«добавляем единицу в R0 (x))4:goto 1 (зацикливаем)Замечание Если основной регистр Rk не упомянут в программе, то ее выполнение никак от негоне зависит.В этом курсе нам важна не сама программа, а доказательство ее существования.Определение 7.5 (Расширенные мини-машины)В расширенных мини-машинах помимо ранее описанных команд существуют команды видаF: f(H1,...Hk) (F, H1..Hk - основные регистры, f — k-арная функция (возможно частичная)),работающая следующим образом: берем регистры H1...Hk, применяем а них f, записываемрезультат в F и увеличиваем на единицу КР.

Назовем их дополнительнымиВ остальном расширенные мини-машины работают аналогично обычным.Определение 7.6nnДве Расширенные мини-машины P0, P1 называются n-эквивалентными, если функции А P А P1совпадают.Теорема 7.1 (об элиминации дополнительных команд)Пусть n∈N и Р - РММ. Если все дополнительные команды Р таковы, что f вычислимы на ММ,то Р n-эквивалентна некоторой обычной минимашине.Доказательство:Пусть f вычисляется программой Pf.

Покажем, как можно убрать из P один операторF:=f(H1...Hk), получив n-эквивалентную ей программу уже с меньшим числом дополнительныхкоманд (от остальных можно избавиться аналогично):Пусть Fi — команда под номером i, тогда пусть L∈N таково, что:1)Все регистры упомянутые в P и Pf — среди P0...PL, и L>k,n. Тогда среди R(L+1), R(L+2),...выберем попарно различные R0*,...RL*. Заменим в Pf все Ri на Ri*, обозначим полученнуюпрограмму Pf*.