{{TIN065 Prednášky}}
==Opakovanie==
Už vieme, že programy a teda ČRFály sa dajú očíslovať. A tiež máme regularizačnú funkciu <math>\rho</math>, ktorá z obecnej rekurzívne spočetnej množiny vyrobí ČRFál a to dokonca tak, že <math>W_{\rho(z)}\subset W_z</math> a tiež <math>\Phi_z=W_{\rho(z)}</math>. A ešte sme si zopakovali triviálne fakty z predchádzajúcej prednášky. Tiež vieme, čo to znamená, že A je B-rekurzívna.
Tak si ešte povieme, čo to znamená, že A je B-rekurzívne spočetná (rekurzívne spočetná vzhľadom k B). Nejde o nič iné ako o to, že A je doménou nejakej B-ČRF. Formálnejšie A je B-rekurzívne spočetná, ak <math>A=dom(\Phi_z(B))</math> pre nejaké z.
Taktiež si zadefinujeme značenie <math>W_{z}^B</math> a <math>W_{z, s}^B</math>. <math>W_{z}^B = dom(\Phi_z(B)) = \{y:\Phi_z(B)(y)\downarrow\}</math> a <math>W_{z, s}^B</math> je konečná množina tých y, ktoré patria do <math>W_{z}^B</math> za s krokov.
==O vzťahu <math>\leq_T</math>==
Pozorovania:
#Vzťah <math>\leq_T</math> je reflexívny a tranzitívny.
#Ak A je rekurzívna množina, tak <math>A\leq_T B</math> pre každé B.
#Ak <math>A \leq_T B</math> a B je rekurzívna, tak aj A je rekurzívna.
Pozorovania sú viac menej zrejmé. Keďže pri <math>\leq_T</math> sa jedná o programy, tak budeme jednotlivé vlastnosti ukazovať pomocou programov (čo je iste pochopiteľnejšie, ako formálne pomocou trojíc <math><\sigma, x, y></math>).
To, že je <math>\leq_T</math> reflexívne (<math>A \leq_T A</math>) je jasné, lebo ak mám orákulum pre A, tak viem zistiť, či prvok patrí do A triviálne. Pre tranzitivitu nech <math>A \leq_T B</math> a <math>B \leq_T C</math>. V tom prípade ak zisťujem, či niečo padne do A a potrebujem sa spýtať na niečo v B, tak miesto orákula pre B použijem program, ktorý počíta B z C a pýtam sa orákula pre C.
Druhé pozorovanie je podobne triviálne. Ak viem A zistiť bez orákula, tak s B-orákulom (akýmkoľvek orákulom) viem A zistiť zas (orákula sa proste nepýtam).
A tretie pozorovanie mi iba hovorí, že ak B viem zistiť (viem zistiť, či nejaký prvok tam patrí), tak nepotrebujem orákulum pre B, ale keď sa budem potrebovať spýtať na B, tak to zistím výpočtom (a preto celé A zistím výpočtom). Alebo inak: mal som program na zisťovanie A, ktorý používal funkciu orákulovu is_in_B a funkciu is_in_B nahradím programom pre B a získam program pre A bez orákula.
==Ekvivalencia <math>\equiv_T</math> a [[wen:Turing degree|T-stupne]]==
Keď mám <math>\leq_T</math>, tak je jednoduché zadefinovať reláciu <math>\equiv_T</math>.
<math>A \equiv_T B</math> ak <math>A \leq_T B \land B \leq_T A</math>. <math>A \equiv_T B</math> je zrejme ekvivalencia a pre ekvivalenciu vieme vyrobiť triedy ekvivalencie. Jedna trieda ekvivalencie potom reprezentuje algoritmicky rovnako zložité množiny. Jednotlivé triedy ekvivalencie sa označujú malým písmenom, pod ktorým je vlnovka (v TeXu snáď \underset{\widetilde{}}{a})) a nazývajú sa "stupne nerozhodnuteľnosti" (degrees of unsolvability). Lepším pojmom sú T-stupne, pretože pre rôzne prevoditeľnosti môžeme rovnakým spôsobom vytvoriť ekvivalenciu a príslušne triedy nazvať 1-stupne, m-stupne, tt-stupne a podobne.
Stupeň <math>[\emptyset]</math> (trieda ekvivalencie reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak mám množinu A, tak <math>deg_T(A)=\{B:B\equiv_T A\}</math> je T-stupeň A (označoval by sa malým a s vlnkou pod).
Pomocou <math>\leq_T</math> na jednotlivých množinách môžem na triedach ekvivalencie zaviesť čiastočné usporiadanie: <math>[A] \leq [B]</math> ak <math>A \leq_T B</math> pre ľubovoľné <math>A \in [A]</math> a <math>B \in [B]</math>. Jasné je, že <math>[\emptyset] \leq [B]</math> pre každé B (z druhej vlastnosti v pozorovaní vyššie).
Mierna odbočka: Ak si vezmeme všetky množiny (no, to je trošku [[Teorie množin|problematické]], ale nevadí), tak si ich rozdelíme podľa našej ekvivalencie a zistíme, že jediná trieda, ktorú môžeme algoritmicky rozhodnúť je práve <math>[\emptyset]</math>. Všetky ostatné stupne sú nerekurzívne, takže algoritmicky nerozhodnuteľné.A preto sa tomu hovorí stupne nerozhodnuteľnosti.
==Očíslovanie a s-m-n veta==
ČRF vieme očíslovať: <math>\{\varphi_x\}</math>. My si ale môžeme zobrať tiež numeráciu <math>\{\Phi_x(\emptyset)\}</math>,l čo sú ČRFály, do ktorých podhodíme rekurzívne orákulum a tie sú rekurzívne izomorfné s ČRF (teda máme preklad z čísel jedného na čísla druhého - existuje rekurzívna permutácia p taká, že <math>\varphi_x=\Phi_{p(x)}(\emptyset)</math>. <math>W_z^\emptyset</math> sú práve všetky rekurzívne množiny.
Tento prístup k funkciám a k množinám je univerzálnejší a preto budeme radšej písať <math>\Phi_x(\emptyset)</math> ako <math>\Phi_x(\emptyset)</math>. Poznámka: Ak budeme používať len <math>\Phi_x(\emptyset)</math> (teda len s rekurzívnou množinou), dostaneme zimný semester (Vyčísliteľnosť I).
Zadefinujeme si, čo je to funkcia prre viac premenných. je to funkcia, kde pošleme kód n-tice premenných: <math>\Phi_z(B)(x_1, x_2, \dots, x_n) \simeq \Phi_z(B)(<x_1, x_2, \dots, x_n>)</math>.
