Звідності. Відносна обчислюваність , Детальна інформація

Розглянемо ЧРФ g(x, y)=(х(у)\xF02DС. За s-m-n-теоремою існує РФ t(x) така, що g(x, y)=(t(x)(у) для всіх х, y. Зафіксуємо х. Тоді для всіх у маємо: (х(у)=C ( (t(x)(у)=0. Звідси (х є константа C ( (t(x) = o. Отже, х(B ( t(x)(A. Тому РФ t(x) : B(m A.

Маємо А(m В та B(m A. Звідси А (m В.

Приклад 2. Покажемо, що {x | (х = o} (m {x | (х є РФ}

Позначимо А={x | (х = o} та В ={x | (х є РФ}.

Розглянемо ЧРФ f(x, y)=0\xF02D(х(у). За s-m-n-теоремою існує РФ s(x) така, що f(x, y)=(s(x)(у) для всіх х, y. Зафіксуємо х. Тоді для всіх у маємо: (х(у)=0 ( (s(x)(у)(. Звідси (х = o ( (s(x) є РФ. Таким чином, х(А ( s(x)(В. Тому РФ s(x) : А(m В.

Розглянемо ЧРФ g(x, y)= o((х(у\xF029\xF029\xF02E За s-m-n-теоремою існує РФ t(x) така, що g(x, y)=(t(x)(у) для всіх х, y. Зафіксуємо х. Тоді для всіх у маємо: (х(у)( ( (t(x)(у)=0. Звідси (х є РФ ( (t(x) = o. Таким чином, х(B ( t(x)(A. Тому РФ t(x) : B(m A.

Маємо А(m В та B(m A. Звідси А (m В.

Приклад 3. Покажемо, що {x | (х є РФ} (m {x | Dх нeскiнчeнна}.

Позначимо А={x | (х є РФ} та В ={x | Dх нeскiнчeнна}.

є ЧРФ за ТЧ. За s-m-n-теоремою існує РФ s(x) така, що f(x, y)=(s(x)(у) для всіх х, y. Зафіксуємо х. Нехай х(А, тобто (х є РФ. Тоді (х(z)( для всіх z, звідки (s(x)(у)=f(x, y)=0 для всіх y. Отже, (s(x) = o, тому Ds(x) = N, звідки s(x)(В. Нехай х(А, тобто (х не є РФ. Тоді існує т(N таке, що (х(т)(. Звідси для всіх y(т f(x, y)(, тому (s(x)(у)(. Отже, Ds(x) скінченна, тому s(x)(В. Маємо х(А ( s(x)(В, тому РФ s(x) : А(m В.

Задамо функцію g(x, y) наступною схемою примітивної рекурсії:

g(x, 0) = (z((х(z)();

g(x, y+1) = (z((х(z)( & z(g(x, 0) & z(g(x, 1) & … & z(g(x, y)).

За ТЧ g(x, y) є ЧРФ, тому за s-m-n-теоремою існує РФ t(x) така, що g(x, y)=(t(x)(у) для всіх х, y. Зафіксуємо х. Нехай х(В, тобто Dx нескінченна. Тоді g(x, y)( для всіх у(N, тому (t(x)(у)( для всіх у(N. Отже, (t(x) є РФ, звідки t(x)(A. Нехай х(В, тобто Dx скінченна. Звідси функція (t(x) скінченна, тому не РФ. Отже, х(А. Таким чином, х(B ( t(x)(A. Тому РФ t(x) : B(m A.

Маємо А(m В та B(m A. Звідси А (m В.

Приклад 4. Покажемо: {x | Dх нeскiнчeнна}(m {x | Ех нeскiнчeнна}.

Позначимо А={x | Dх нeскiнчeнна} та В ={x | Ех нeскiнчeнна}.

За s-m-n-теоремою існують РФ s(x) та t(x) такі, що для всіх х\xF0CEN Еs(x)=Dx та Dt(x)=Еx (приклади 4 та 5 розділу 7.3). Тому х(А ( s(x)(B та х(B ( t(x)(A. Отже, s(x) : А(m В та t(x) : B(m A. Звідси А (m В.

Наслідок. {x | (х = o} (m {x | (х є константа C} (m {x | (х є РФ} (m

(m {x | Dх нeскiнчeнна}(m {x | Ех нeскiнчeнна}.

Приклад 5. Покажемо, що D (m {x | (х є РФ}.

є ЧРФ за ТЧ. За s-m-n-теоремою існує РФ s(x) така, що (s(x)(у)=f(x, y) для всіх х, y. При х(D маємо (s(x)(у)=f(x, y)=g(y) для всіх y, звідки (s(x)=g є РФ, тому s(x)(А. При х(D маємо (s(x)(у)( для всіх y, звідки (s(x)=f( не є РФ, тому s(x)(А. Отже, х(D ( s(x)(А, тому РФ s(x) : D (m А.

Приклад 6. Покажемо, що D (m {x | Dх є РМ}.

за ТЧ є ЧРФ. За s-m-n-теоремою існує РФ s(x) така, що (s(x)(у)=f(x, y) для всіх х, y. При х(D маємо Рх(х)(, тому iснує t таке, що Рх(х)( за t крокiв. Для кожного у(t Рх(х)( за (у крокiв, звідки f(x, y)( для всіх у(t. Звідси (s(x)(у)( для всіх у(t, тому (s(x) скінченна. Отже, Ds(x) є РМ. Таким чином, при х(D маємо s(x)(А.

Нехай тепер х(D. Звідси Рх(х)(, тому для кожного у(N Рх(х) не зупиниться за (у крокiв. Отже, для всіх у(N (s(x)(у)=f(x, y)=g(у). Звідси Ds(x)=Dg не є РМ, тому s(x)(А.

Маємо х(D ( s(x)(А, тому РФ s(x) : D (m А.

Введемо класи eквiвалeнтностi вiдносно (m : dm(A)={B | A(mB}. Такi класи eквiвалeнтностi будемо називати m-стeпeнями.

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

a(m b, якщо A(mB для всiх A\xF0CEa, B\xF0CEb\xF02E

Будeмо писати a