Вопрос 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<sub>1</sub> 0 `y₂ 0…0 `y_k 0

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

t=C(t₁,C(код a , код b))

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

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

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

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

t=C(z,C(t_1,C(код a’,код b’)))

Если 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 – нерекурсивно.

Вопрос 27. Геделевская нумерация формул, аксиом и правил вывода исчисления предикатов. Рекурсивно перечислимые множество…

Гёделевская нумерация формул, аксиом и правил вывода исчисления предикатов.

Разрешимые и неразрешимые элементарные теории.

S={+⁽²⁾, × ⁽²⁾, S⁽¹⁾, 0⁽⁰⁾, ≤ ⁽²⁾}

Константа 0 с(0,1)

Переменные v_k с(1,k)

Термы: S(t₁) с(2, код t₁)

t₁+t₂ с(3, с(код t₁, код t₂))

t₁×t₂ с(3, с(код t₁, код t₂))

Атомарные формулы: t₁≈t2 с(5, с(код t₁, код t₂))

t₁Ít₂ с(6, с(код t₁, код t₂))

Формулы: φÙy с(7, с(код φ, код y))

φÚy с(8, с(код φ, код y))

φ®y с(9, с(код φ, код y))

^Øφ с(10, код φ)

$ v_n φ с(11, с(n, код φ))

" v_n φ с(12, с(n, код φ))

Секвенция φ₁,…φ_n y с(13, сⁿ⁺¹(код φ₁,… код φ_n, код y))

{n ½ n – код некоторой формулы} – ПРО (примитивно рекурсивное отношение)

æ1, если n – код формулы и v_s входит в эту формулу свободно

ПРФ F_r (r,s)= í

è0, в противном случае

Sb(код φ, n, код t)=код ((φ)_t^vn) – РФ

æ1, если n – код i-ой аксиомы

ПРФ A_i (n)= í

è0, в противном случае

æ1, если секв. с кодом k получается из секв. с кодами m, n по правилу 1

ПРФ R₁ (n,m,k)= í

è0, в противном случае

Рекурсивно перечислимые множества.

Теорема: множество номеров доказуемых формул ИП^S рекурсивно перечислимо.

Следствие: если X - рекурсивно перечислимое множество номеров формул, то тогда

{код φ ½x φ} – рекурсивное множество.

Теорема о неразрешимости элементарной арифметики: если X – непротиворечивое множество формул, X≥A_o, то T={код φ ½ x φ, φ - предложение} нерекурсивно.

Теорема Гёделя о неполноте арифметики Пеано: если X – непротиворечивое рекурсивное

расширение A_o, то {код φ ½ x φ и φ - предложение} – неполная теория.

Теорема Чёрча о неразрешимости ИП^S: множество номеров доказуемых в ИП^S формул не рекурсивно.

Вопрос 28. Временная и ленточная сложности МТ, вычисляющей заданную функцию. Теоремы о верхней границе сложности вычислений. Теорема об ускорении

t_T(x) – временная сложность, число тактов машины Т для вычисления функции f(x). Если функция f(x) не определена, то t_T(x) неопределенна.

Активной зоной при работе машины Т на числе Х называется связное мн-во, содержащие все ячейки ленты, которые были активными (т.е. использовались при вычислении значения функции) в процессе работы машины Т.

S_T(x) – длина активной зоны при работе машины Т на числе х, если f(x) не определена, то и функция S_T(x) неопределенна.

S_T(x) – ленточная сложность машины Т

T = <{a₀,a₁...a_n}, {q₀,q₁,...q_m}, П>

S_T(x) ≤ x+1+t_T(x)

t_T(x) ≤ (m+1)S_T²(x)*n^S_T^(x)