45. Нерозв’язність проблем зупинки та самозастосованості. Наслідки.

Масова проблема алгоритмічно розв'язна, або розв'язна, якщо відповідний предикат рекурсивний, інакше проблема алгоритмічно нерозв'язна, або нерозв'язна.

Масова проблема частково алгоритмічно розв'язна, або частково розв'язна, якщо відповідний предикат є ЧРП.

Проблема зупинки формулюється так: за x та y встановити, чи є визначеним значення _x(y). Проблема самозастосовності формулюється так: за x встановити, чи є визначеним значення _x(x).

Теорема 4.2.7. Предикати "_x(x)" і "_x(y)" нерекурсивні, тобто проблеми самозастосовності та зупинки алгоритмічно нерозв'язні.

Наслідок 1. Існують нерекурсивні ЧРП та нерекурсивні РПМ

Наслідок 2. Клас РПМ незамкнений відносно операції доповнення.

Наслідок 3. Клас ЧРП незамкнений відносно логічної операції .

Наслідок 4. Мають місце наступні строгі включення:

ПРФРФЧРФ; СМПРМРМРПМ; ПРПРПЧРП

46.Індексні множини. Теорема Райса, її значення. Дуальна до теореми Райса. Теорема Райса-Шапіро.

Нехай  : N→ – ефективна нумерація множини об'єктів , нехай . Множину номерів всіх об'єктів із  позначимо N(), тобто N()=^–1(). Множини вигляду N(), де ЧРФⁿ (зокрема, ЧРФ¹), будемо називати індексними множинами.

Теорема 4.3.1 (Райс). Нехай ЧРФⁿ та . Тоді N() не є РМ.

Наслідок. Нехай РПМ та . Тоді N() не є РМ.

Теорема Райса стверджує, що жодна нетривіальна властивість в класах всіх n-арних ЧРФ та всіх РПМ не може бути ефективно розпізнана!

Теорема 4.3.2. Нехай ЧРФⁿ та f_. Тоді N() не є Р

Теорема 4.3.3 (Райс-Шапіро). Нехай ЧРФⁿ така, що N() є РПМ. Тоді для довільної функції fЧРФⁿ маємо: f  існує скінченна функція  така, що  f та .

47.Звідності.M-звідність, її властивості. M-степені, їх властивості.

Проблема  зводиться до проблеми , якщо із розв'язності  випливає розв'язність . Отже, якщо нерозв'язна проблема  зводиться до проблеми , то  теж нерозв'язна. Метод нумерацій дозволяє масові проблеми подавати за допомогою певних числових множин, тому обмежимося розгля-дом звідності множин. Існують різні уточнення поняття звідності множини A до множини B. Ці уточнення відрізняються за способом використання та об'ємом інформації про множину B, яку можна використати для розв'язку питання про множину A. В даному посібнику розглянемо два найпоширеніші уточнення поняття звідності множин – m-звідність та T-звідність.

m-звідність та 1-звідність. m-степені

Множина A m-зводиться до множини B, якщо існує РФ g така, що для всіх xN xA  g(x)B. Це записуємо у вигляді A_m B, або g: A_m B, якщо треба вказати, що саме РФ g m-зводить A до B.

Будемо писати A<_m B, якщо A_m B та невірно B_m A.

Писатимемо A |_m B, якщо невірно A_m B та невірно B_m A.

Введемо відношення m-еквівалентності: A_mB  A_m B та B_m A.

Окремим випадком m-звідності є 1-звідність.

Множина A 1-зводиться до множини B (записуємо A₁B ), якщо існує ін'єктивна РФ g така, що для всіх xN xA  g(x)B.

Аналогічно вводиться відношення <₁ , |₁ та 1-еквівалентності ₁.

Вкажемо елементарні властивості m-звідності та 1-звідності.

r1) Якщо A₁B, то A_m B.

r2) Відношення ₁ та _m рефлексивні і транзитивні.

r3) A_m B  _m ; те ж вірне для ₁.

r4) Якщо A_m B та B є РМ, то A є РМ; те ж для ₁.

r5) Якщо A_m B та B є РПМ, то A є РПМ; те ж для ₁.

r6) Якщо A є нерекурсивна РПМ, то невірно A_m та невірно _m A; те ж для ₁.

r7) A_m N  A=N; те ж для ₁.

r8) A_m   A=; те ж для ₁.

r9) N_m A A.

r10) N₁A  A має нескінченну рекурсивно перелічну підмножину.

r11) _m A  AN.

r12) Якщо A рекурсивна і B та BN, то A_m B.

r13) Для довільної множини B маємо A_m AB та A_m BA.

r14) Для довільної множини B маємо A_m AB та A_m BA.

r15) Для довільної AN маємо A₁AN та AN _m A

Введемо класи еквівалентності відносно _m : d_m(A) = {B | A_mB}.

Такі класи еквівалентності будемо називати m-степенями.

Відношення _m індукує на множині m-степенів відношення часткового порядку, якe теж будемо позначати _m :

a_m b, якщо A_mB для всіх Aa, Bb.

Будемо писати a<_m b, якщо a_m b та a  b.

Писатимемо a|_m b, якщо невірно a_m b та невірно b_m a.

m-степінь рекурсивна, якщо вона містить РМ.

m-степінь рекурсивно перелічна (РП), якщо вона містить РПМ.

Аналогічно визначаються 1-степені та відношення ₁ на множині 1-сте-пенів, визначаються рекурсивні та рекурсивно перелічні 1-степені.

Зрозуміло, що кожна m-степінь складається із 1-степенів.

Із r4 та r5 випливає, що кожна рекурсивно перелічна m-степінь складається тільки з РПМ, кожна рекурсивна m-степінь складається тільки з РМ. Те ж вірне для 1-степенів.

Згідно r7 та r8 існують 2 специфічні рекурсивні m-степені, які складаються з єдиної множини: 0 = d_m()={} та n = d_m(N) = {N}. Згідно r4 та r12 всі інші РМ утворюють рекурсивну m-степінь 0_m .

Визначимо також рекурсивно перелічну m-степінь 0'_m = d_m(D).

Із r4, r5, r7, r8, r12 маємо елементарні властивості m-степенів:

d1) 0_m_m a для всіх m-степенів a  0,  n.

d2) n_m a для всіх m-степенів a  0 .

d3) 0_m a для всіх m-степенів a  n.

d4) Якщо a_m b і m-степінь b є РП, то m-степінь a теж є РП.

Точною верхньою гранню m-степенів a та b назвемо m-степінь c:

– a_m с та b_m с;

– с_m d для кожної m-степені d такої, що a_m d та b_m d.

Теорема 5.1.1. Для кожної пари m-степенів a та b існує єдина точна верхня грань ab = d_m(AB), де Aa та Bb.