Вопрос 21.Примитивно рекурсивные отношения, основные преобразования над ними…

P(подмножество) N^k

P наз-ся ПРО если

Везде x и над ним черта

χ_з(x сверху черта)={1,если x є P 0, в другом случае)

Является ПРФ

χ_з - 1)индикаторная, 2)характеристическая функция

Утв 1. Если P,Q є N^k то P^Q,PUQ,P->Q,~P,PxR-ПРО

Док-во:

χ_p^q(x)= χ_p(x)* χ_q(x)

χ_~p(x)=~sgχ_p(x)

PUX=~P^~Q

χ_pxr(x,y)= χ_p(x)* χ_r(y) (y тоже сверху подчеркнуто)

PxQ={x^y| x є P, y є R}

Ограниченные кванторы

P(подмн-во) N^k+1

Q₁(x,y) : (сущ. z <= y) P(x,z) (x сверху подчеркнуто )

Q₂(x,y) : (люб. Z <=y) P(x,z) (ост. нет и далее так же)

Утв.2: Если Р – ПРО, то Q₁ и Q₂ – ПРО

Док-во:

χ _q1(x,y)=sg(∑ (i=0,y) χ_p (x,i))

x_q2(x,y)=П(I=0,y) χ_p(x,i)

Примеры ПРО (ничто сверху не подчеркнуто)

1)x=y: χ(x,y)=~sg(|x-y|)

2)x<=y: χ=(сущ z<=y)(x+z=y)

3)x<y: χ=(сущ z<=y)(s(x+z)=y)

4)x/y : χ=~sg(rest(x,y)-остаток от деления x на y

(y делит x без остатка)

5)P(x):x-простое число

люб. z<=x(x/z->(z=xUz=s(o(x)))^x>=2

Вопрос 22. Нумерация n-ок натуральных чисел примитивно рекурсивными ф-ями.

0 1 3

(0,0)→ (0,1) (0,2) (0,2)

2 4

(0,0)→ (0,1) (0,2) (0,2)

5

(0,0)→ (0,1) (0,2) (0,2)

l(x,y)=n, l(n)=x – левая координата числа n, r(n)=y –правая координата числа n.

n = c( l(n),r(n) ), x = l( c(x,y) ), y = r(c(x,y))

c(x,y) = [(x+y)(x+y+1)/2]+x

[ ( [ [√(8n+1)]+1 ] ·-1 )( [[√(8n+1)]+1] ) ]

l(n) = n·- [ ( [ 2 ] )( [ 2 ]) ]

[ 2 ]

r(n) = [ [√(8n+1)]+1 ] ·- (l(n)+1)

[ 2 ]

c²(x,y) = c(x,y), c₁² (n) = l(n), c₂²(n)=r(n)

cⁿ: Nⁿ ↔ N – нумерация n-ок (c₁ⁿ, c₂ⁿ,…, c_nⁿ)

c₁ⁿ⁺¹(n)= c₁ⁿ l(n)

c₂ⁿ⁺¹(n)= c₂ⁿ l(n)

c_nⁿ⁺¹(n)= c_nⁿ l(n)

c_n+1ⁿ⁺¹(n)= r(n)

Вопрос 23. Частично рекурсивные и рекурсивные функции. Теорема об элиминации.

Оператор минимизации: M(g⁽ⁿ⁺¹⁾,h⁽ⁿ⁺¹⁾)=f⁽ⁿ⁾

f(x )= y(g(x ,y) ≤ h(x,y))

Наименьший y т.ч. g(x ,y) ≤ h(x,y) и i<y g(x ,i ) ,h(x,i ) определены и g(x ,i ) >h(x,i )

Функция f : A N ,где AN^(k) называется частично рекурсивной ,если существует последовательность f₀ … f_n т. ч. f(n)=f и  i функция f_i яв-ся простейшей ПРФ или получается из пред. функций операторами S ,R,M .

ЧРФ называется рекурсивной , если A= N^k т. е. функция всюду определена.

ПРФ  РФ ЧРФ  быстрорастущие функции.

f(x)= y(s(x) ≤ x)

Теорема об элиминации примитивной рекурсии.

Особая ЧРФ м.б. получена из простейших и функций + , * с помощью операторов подстановки(S) и минимизации(M).

Вопрос 24. Вычислимость чрф на машинах Тьюринга.

1) ЧРФ

2) Функции , правильно вычистимые на машинах Тьюринга.

1)  2)

a)Iⁿ_m(x_1… x_n)= x_m

q₁0x_n-10…0 x_n0 > q₀ 0 x_m00…0

Ц_n^n-m+1 (Б⁺)^n-1(ЛБ^-)^n-1

б) s(x)=x+1 - Машина S

в) о(x)=0

q₁01^x+10> q₀010^x0 - Машина ЛS

г)сложение , умножение

д) суперпозиция S : f(g₁(x),…. g_n(x))

е) минимизация: f(x )= y(g(x ,y) ≤ h(x,y))

Пример: x-y y0 > RБ^-Е > x=0 Б⁺ЛБ^-

q₁ 0x 0 y 0>E y=0 > ЛБ^- x0 R Б⁺ A

Б⁺

2)1) Любая вычислимая на м.Т. функция частично рекурсивна.