Вопрос 20. Понятие примитивно рекурсивной функции. Основные примеры. Простейшие прф:

1. I_mⁿ (x₁,…,x_n) = x_m, m  n

2. S(x)=x+1

3. o(x)=0

Операторы:

1. S (оператор подстановки)

S (f⁽ⁿ⁾,g₁^(k),g_n^(k))(x) = f(g₁(x),…,g_n(x))

x = (x₁,…,x_k)

2. R (оператор примитивной реурсии)

R(f⁽ⁿ⁺²⁾, g⁽ⁿ⁾)= h⁽ⁿ⁺¹⁾

h(x,0) = g(x)

h(x,y+1) = f(x,y,h(x,y))

Функция f называется примитивно рекурсивной, если существует последовательность f₀,f₁,…,f_n , такая что f_n=f и  i  n. Функция f_i является простейшей ПРФ или получается из предыдущих функций с помощью операторов S и R.

Примеры:

1) x+y x+0 = I₁¹(x)

x+(y+1)=S(x+y)

2) x*y x*0 = o(x)

x*(y+1) = S(x+y)

3) x! = 1*2*3…x, 0!=1

4) x^y, где x⁰ = 1

5) [x/y] = d, если y 0

[x/y] = x, если y = 0

x = dy + r, r<y

6) rest(x,y) = r, если y  0

rest(x,y) = r, если y = 0

7) n  P_n – n-е простое число.

(P₀=2, P₁=3, P₂=5, …)

8) ex(x,y) = показатель степени P_y в разложении числа x на непротиворечивые множители, если x0.

ex(x,y) = 0, в противном случае.

X=P₀^{h 0} P₁^h1… P_k^hk, ex(x,y) = h_y

Вопрос 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)