{{TIN065 Prednášky}} Na vyčísliteľnosti I sme mali 1-prevoditeľnosť: A1BA\leq_1 B znamená, že existuje prostá ORF funkcia f, pre ktorú platí, že aAf(a)Ba \in A \Leftrightarrow f(a) \in B.

Okrem tejto prevoditeľnosti existuje množstvo ďalších - napríklad známa m-prevoditeľnosť, ktorá sa od 1-prevoditeľnosti líši tým, že nepožaduje, aby funkcia f bola prostá (m\leq_m), potom "truth table" prevoditeľnosť (tt\leq_{tt}), "weak truth table" prevoditeľnosť (wtt\leq_{wtt}) a pre nás najzaujímavejšia turingovská prevoditeľnosť (T\leq_{T}). Prevoditeľnosť slúži na to, aby sme vedeli zistiť, či nejaký prvok je prvkom množiny A na základe toho, že vieme o nejakých prípadne iných prvkoch zistiť, či sú prvkami množiny B.

Truth table reducibility

AttBA \leq_{tt} B znamená, že existuje ORF, ktorá každému xAx \in A priradí n-árnu boolovskú funkciu α\alpha a tiež n-ticu bodov y1,y2,...,yny_1, y_2, ..., y_n takých, že CA(x)=truexAα(CB(y1),CB(y2),,CB(yn))=trueC_A(x) = true \Leftrightarrow x \in A \Leftrightarrow \alpha(C_B(y_1),C_B(y_2), \cdots, C_B(y_n)) = true, kde CAC_A je charakteristická funkcia AA a CBC_B je charakteristická funkcia BB. (Spomínaná ORF teda priradí každému xx kód funkcie α\alpha a hodnoty ypsilónov).

Priradenie funkcie α\alpha ako aj premenných yiy_i je závislé na xx, takže pre rôzne xx môžu byť rôzne α\alpha aj yy. Pekné na funkcii α\alpha je, že je definovaná všade a to nezávisle na množine BB, pretože to je boolovská funkcia. A boolovská funkcia sa dá zapísať pravdivostnou tabuľkou - odtiaľ názov "truth table" redukcia (poznámka: boolovských funkcií na nn premenných je 22n2^{2^n}). Príklad množín, ktoré sú na seba prevoditeľné, je K\overline{K} a KK. K prvku xx priradíme prvok xx (ten istý) a α\alpha bude negácia (poznámka: 1-previesť sa nám ale K\overline{K} na KK nepodarí).

K tomuto môžeme vymyslieť nejaké obmedzenia, či už na nn (takže sa spýtame na najviac nn prvkov), prípadne na tvar funkcie α\alpha. Tým sa teraz nebudeme zaoberať. Tiež prevoditeľnosťou "weak truth table" sa budeme zaoberať až časom.

T-prevoditeľnosť

Čo nás bude zaujímať viac, je T-prevoditeľnosť. Budeme potrebovať orákulum - hypotetické zariadenie, ktoré odpovedá na otázky "Je yy prvkom BB?". Prípadne si môžeme predstaviť, že máme orákulovu pásku, na ktorej je zapísaná charakteristická funkcia množiny B.

Neformálne: ATBA \leq_T B ak existuje program, ktorý počíta charakteristickú funkciu množiny AA, pričom sa občas môže spýtať, či nejaké yy, ktoré počas svojej práce vypočíta, je prvkom množiny BB.

Keďže hovoríme o programe, zišiel by sa programovací jazyk. Prvá možnosť je použiť BB-ČRF. B-čiastočne rekurzívne funkcie sú také, ku ktorým okrem už známych základných funkcií (nula, nasledovník, projekcia) existuje aj ďalšia - a to práve charakteristická funkcia množiny BB, teda CBC_B. Tá slúži na zistenie, či nejaký prvok je prvkom množiny BB. Takže B-ČRF sú rozdielne pre každé BB. Inak povedané: BB je vlastne množinová premenná. Operátory ostávajú rovnaké ako pri obyčajných ČRF.

Definícia pre Pascal-like jazyk (nazvaný tiež aj B-pascal) je, že pridáme k programu funkciu is_in_B(x:integer):boolean, ktorá vráti truetrue ak xx je prvkom BB a falsefalse ak xx nie je prvkom BB. Táto funkcia si svoj výsledok zisťuje "iným spôsobom" - pýta sa, či už užívateľa alebo orákula. Pre Turingov stroj si zasa môžeme zaviesť "orákulovu pásku", ktorú stroju pridáme (ako ďalšiu pásku), na ktorej bude mať CBC_B (takže napríklad na tejto páske na pozícii ii bude 00, ak iBi \notin B a 11 ak iBi \in B).

Chcelo by to ukázať, že všetky tieto možnosti zavedenia sú ekvivalentné.

To, že B-ČRF môžeme reprezentovať Turingovým strojom s orákulom alebo B-Pascalom je viac menej vidieť. Ukáže sa to rovnako ako pri obyčajných ČRF - sú vybudované induktívne. Opačným smerom použijeme mierne všeobecnejší postup.

Výpočtový strom

Predstavme si program P so vstupmi B (množina) a x (číslo): P(B, x). To, ako náš program počíta sa dá nakresliť do výpočtového stromu.

Image:Vypoctovy%20strom.PNG

Tento strom zachytáva všetky možné scenáre behu programu pre ľubovoľný vstup xx a ľubovoľnú množinu BB. Program dostane na vstupe xx a množinu BB. Výpočet potom prebieha podobne ako výpočet bežného programu definovaného klasickou ČRF. Rozdiel je však v tom, že naviac je povolená operácia <em>otázky</em>. To znamená, že sa behom výpočtu je možné spýtať, či je nejaké yiy_i prvkom množiny BB. Podľa toho, aká bude odpoveď, sa je možné vo výpočte rozhodovať a následne sa vydať po ľavej či pravej vetve stromu. Týchto otázok je povolený neobmedzený počet. Výpočet môže dopadnúť rôzne. Buď skončí (na obrázku úplne ľavá vetva) alebo sa "zacyklí" (druhá vetva zľava). To, čo je pre nás dôležité je, že každý konečný výpočet sa skončí po konečnom počte krokov.

Kľúčové miesto

Množina konečných vetiev výpočtového stromu je rekurzívne spočítateľná. Nahliadne sa to tak, že prehľadávaním do šírky môžeme prejsť celý strom a tak efektívne vygenerovať všetky jeho konečné vetvy.

Tiež si môžeme vymyslieť aj rekurzívne spočítateľnú množinu WW, ktorá obsahuje štvorice <x,y,u,v><x, y, u, v>, kde xx je vstup programu, yy je jeho výstup a uu a vv sú indexy konečných množín, ktoré vyrobíme tak, že keď ideme po vetve v strome od xx k yy (beží nám program), tak pri rozhodovaní sa, či yiy_i je prvkom množiny BB uložíme yiy_i do množiny s indexom uu ak yiy_i je prvkom množiny BB a ak yiy_i nie je prvkom množiny BB, tak yiy_i uložíme do množiny s indexom vv. Indexy uu a vv na začiatku reprezentujú kód prázdnej množiny a postupne sa menia tak, že do odpovedajúcich množín pridávame práve rozhodované yiy_i podľa príslušnosti do BB. Ak v strome na obrázku pôjdeme stále vľavo, tak DuD_u (množina s indexom uu) bude prázdna a DvD_v bude obsahovať y0y_0 a y1y_1.

Potom platí: P(B,x)=yP(B, x) = y práve vtedy, keď

ParseError: KaTeX parse error: Undefined control sequence: \and at position 35: …y, u, v> \in W \̲a̲n̲d̲ ̲D_u \subset B \…

.

{{TODO|Nasledujúci odstavec som nepochopil, takže je to tu napísané len "ako som to zaznamenal".}} <TIN064%20Rekurzivní%20spočetnost#Některé%20z%20vlastností> bola veta, že ČRF má rekurzívne spočítateľný graf. Tiež sa hovorilo, že by mala existovať nejaká rekurzívne spočítateľná podmienka (v našom prípade by mala byť podmienkou tá vec, s <x,y,v,u><x, y, v, u>, ktoré je prvkom WW). A my si z toho vytvoríme rekurzívnu podmienku tak, že miesto u,v\exists u, v napíšeme u,v,s\exists u, v, s a ss prehlásime za nejaký počet krokov (a BB za rekurzívnu, pretože máme CBC_B) a tak máme BB-rekurzívnu podmienku. A z toho, že to vieme takto vyjadriť je funkcia Φz,sB\Phi_{z, s}^{B} B-ORF?

A ešte sa na prednáške zopakovali definície, čo je to binárny reťazec (string) - konečná postupnosť núl a jedničiek. A tiež čo to znamená, že σ\sigma je začiatkom (prefixom) τ\tau (normálne to značíme σ\sigma \preceq τ\tau, ale na tejto Wiki z technických dôvodov στ\sigma \leq \tau). A ešte sme si povedali, že BB a CBC_B stotožníme a že teda môžeme mať aj "prefix" množiny. A tiež, že množiny môžeme viac menej namapovať na reálne čísla medzi nulou a jednotkou. Problémy sú s číslami ako 0.10.1 a 0,01111111...0,01111111..., ktoré sú rovnaké, ale predstavovali by inú množinu. A teda množín, s ktorými budeme pracovať, je nespočítateľne veľa.