Вопрос 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) Любая вычислимая на м.Т. функция частично рекурсивна.

Вопрос 25. Частичная рекурсивность функций , вычислимых на машинах Тьюринга.

Теорема: следующие отношения примитивно рекурсивны

1. Т₀(h,x,y,t)  машина с кодом начиная работу на слове с кодом x ,заканчивает работу на слове с кодом y ,менее чем за t шагов в состоянии q_0.

x=>y

2) T^k(h,y_1….. y_k ,z,t)  машина с кодом n , начиная работу на слове q₁ 0 y₁ 0 y₂ 0…0 y_k 0

заканчивает работу менее чем за е(t) шагов , на слове  q₀ 0 z 0  , где r(t)=C(код ,код  )

t=C(t₁,C(код  , код ))

Следствие: Если функция f(y_1… y_k) – вычислима на м.Т.  существует nN т.ч. f(y_1… y_k)=l(t(T^k(n, y_1… y_k,),e(t),r(t))=1)=(n, y_1… y_k)

Доказательство:

n- код м.Т. , которая вычисляет f

n =код (T(f), f(y_1… y_k)) вычисляется за t₁ шагов

t=C(z,C(t_1,C(код ’,код ’)))

Если f –вычислима на м.Т. ,то f -ЧРФ

Вопрос 26. Универсальное чрф. Теорема роб универсальности. Теорема Райса.

Ф-я ƒ(n,x₁,…x_k) – универсальная для класса ф-ий K, если:

1) для  фиксированной n_o (ƒ(n_o,x₁,…x_k): N^k→N)

2) для  ф-ии g  K n_o  N, так что значение ƒ(n_o,x₁,…x_k)=g(x₁,…x_k)

Теорема об универсальности: 1) φ(x_o,y)=l(μt(T¹(x_o,y,l(t),r(t))=1)) является универсальной ф-ей для класса одноместных ЧРФ.

2) φ^s(x_o,x₁,…x_s)=φ(x_o,c^s(x1,…x_s)) – универсальная для класса S-местных ЧРФ.

Теорема о -ии ЧРФ v(x), которую нельзя определить до рекурсивной ф-ии:

Доказательство: v(x)=sgφ(x,x) – ЧРФ. v(x) не доопределима до РФ.

Предположим противное: v_o(x) – РФ, доопределяющая ф-ию v(x).

v_o(x)=φ(n,x) для некоторого n.

v_o(x)=φ(n,x)

sgφ(x,x)  противоречие

Теорема Райса:

Пусть F – некоторое непустое семейство однородных ЧРФ не совпадающих с классом всех одноместных ЧРФ. Тогда множество N_F номеров всех ф-ий, входящих в F – нерекурсивно.