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

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

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

={+⁽²⁾,  ⁽²⁾, 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₂))

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

φ с(8, с(код φ, код ))

φ с(9, с(код φ, код ))

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

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

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

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

{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, в противном случае

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

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

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

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

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

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

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

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

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

О верхней оценке сложность вычислений

Существует ли рекурсивная ф-ия h(x), т.ч для любой вычислимой ф-ии f(x) существует машина T, вычисляющая её за время t_T(x)≤h(x) (если f(x) определена)?

Теорема: Для любой рекурсивной функции h(x) существует рекурсивная ф-ия f(x), т.ч.

_f ={0,1) и для любой машины Т, вычисляющей эту ф-ию найдется такое x=n, при котором t_T(n)>h(n).

Док-во:

f(x) = { sg_x(x) если _x(x) определено и t_Tx(x) ≤ h(x),

0 иначе

где _x(x) – ф-ия с номером x, соотв. машине T_x с номером x.

n- номер функции f, с условием, что f=_n

T X	0	...	n
T0	tT0(0) ≤h(0)
...		......
Tn			tT0(n) ≤h(n)

f(n) = sg_n(n) =>f(x) ≠ _x(x) т.к _x(x) ≠ sg_x(n)

Если T_n вычисляет f(x), то условие t_Tn(n) ≤ h(n) нарушено.

Сложно вычислимые функции

Теорема Для любой Р.Ф. h(x) существует Р.Ф. f(x) т.ч _f ={0,1) и для любой машины Т, вычисляющей f(x), начиная с некоторого X выполняется условие t_T(x) > h(x)

Теорема об ускорении

Для любой Р.Ф. r(x) сущ. Р.Ф. f(x) с условием, что _f ={0,1), т.ч какова бы ни была машина Т_i, вычисляющая ф-ию f(x) найдется машина T_j, вычисляющая эту функцию с условием, что t_Ti(x) > r(t_Tj(x)), начиная с некоторого x

Пример.

r(x) = 2^x

t_Tj < log₂(t_Ti(x))

t_Tk< log₂log₂(t_Ti(x))