{{TIN065 Prednášky}}
Na vyčísliteľnosti I sme mali 1-prevoditeľnosť: <math>A\leq_1 B</math> znamená, že existuje ORF funkcia, pre ktorú platí, že <math>a \in A \Leftrightarrow f(a) \in B</math>.
Okrem tejto prevoditeľnosti existuje množstvo ďalších - známa m-prevoditeľnosť (<math>\leq_m</math>, potom "truth table" prevoditeľnosť (<math>\leq_{tt}</math>, "weak truth table" prevoditeľnosť (<math>\leq_{wtt}</math>) a pre nás najzaujímavejšia turingovská prevoditeľnosť (<math>\leq_{T}</math>). Prevoditeľnosť slúži na to, aby sme vedeli zistiť, či nejaký prvok patrí do A ak vieme o prvkoch zistiť, či patria do B.
===Truth table reducibility===
<math>A \leq_{tt} B</math> znamená, že existuje ORF, ktorá každému <math>x \in A</math> priradí n-árnu boolovskú funkciu <math>\alpha</math> a tiež n-ticu bodov <math>y_1, y_2, ..., y_n</math> takých, že <math>C_A(X) \leftrightarrow x \in A \leftrightarrow \alpha(C_B(y_1),C_B(y_2), \cdots, C_B(y_n))</math>, kde <math>C_A</math> je charakteristická funkcia <math>A</math>. (ORF samozrejme priradí kód funkcie <math>\alpha</math> a ypsilónov).
Priradenie funkcie <math>\alpha</math> ako aj premenných <math>y_i</math>je závislé na <math>x</math>, takže pre rôzne <math>x</math> môžu byť rôzne <math>\alpha</math> aj <math>y</math>. Pekné na funkcii <math>\alpha</math> je, že je definovaná všade a to neyávisle na množine <math>B</math>, 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 <math>n</math> premenných je <math>2^{2^n}</math>).
Príklad množín, ktoré sú na seba prevoditeľné, je <math>\overline{K}</math> a <math>K</math>. K prvku <math>x</math> priradíme prvok <math>x</math> (ten istý) a <math>\alpha</math> bude negácia (poznámka: 1-previesť sa nám ale <math>\overline{K}</math> na K nepodarí)
K tomuto môžeme vymyslieť nejaké obmedzenia, či už na <math>n</math> (takže sa spýtame na najviac <math>n</math> prvkov), prípadne na tvar funkcie <math>\alpha</math>. 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 "patrí y do B?". Prípadne si môžeme predstaviť, že máme orákulovu pásku, na ktorej je zapísaná charakteristiká funkcia množiny B.
Neformálne: <math>A \leq_T B</math> ak existuje program, ktorý počíta a občas sa spýta na nejaké <math>y</math>, ktoré počas svojej práce vypočíta, či patrí do <math>B</math>.
Keďže hovoríme o programe, zišiel by sa programovací jazyk. Prvá možnosť je použiť B-Č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 <math>C_B</math> - zistenie, či prvok patrí do B (takže B-ČRF sú rozdielne pre každé B: B je množinová premenná). Operátory zostá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 B(x:integer), ktorá vráti 1 ak x patrí do B a 0 ak nepatrí (lepší názov pre funkciu by bol asi is_in_B). Tá 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 druhú pásku), na ktorej bude mať <math>C_B</math> (takže napríklad na pozícii <math>i</math> na páske bude 0, ak <math>i \notin B</math> a 1 ak <math>i \in B</math>).
Chcelo by to ukázať, že všetky tieto možnosti zavedenia sú ekvivalentné.
To, že B-ČRF môžeme reprezentovať TS alebo B-pascalom je viac menej vidieť. Postup je rovnaký ako pri obyčajných ČRF - sú vybudované induktívne. Opačným smerom použijeme mierne obecnejší postup.
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 strom.PNG]]
Tento strom zachycuje všetky scenáre behu programu pre vstup x pre nejakú každú množinu B. Program dostane x, nejak počíta, potrebuje sa spýtať na nejaké <math>y_0</math> a podľa toho, či <math>y_0</math> patrí alebo nepatrí do B sa rozhodne vydať sa po ľavej či pravej vetve stromu (a prípadne sa môže pýtať znova). Takto beží, až kým neskončí (na obrázku úplne ľavá vetva) alebo kým "nezacyklí" (druhá vetva zľava). To, čo je pre nás dôležité je to, že každý končiaci výpočet skončí po konečne mnoho krokoch.
Kľúčové miesto: Množina konečných vetiev výpočtového stromu je rekurzívne spočetná. Prehľadávaním do šírky prechádzam stromom a efektívne generujem všetky konečné vetvy.
Tiež si môžeme vymyslieť aj rekurzívne spočetnú množinu W, ktorá obsahuje štvorice <x, y, u, v>, kde x je vstup programu, y je jeho výstup a u a v sú indexy konečných množín, ktoré vyrobíme tak, že keď ideme po vetve v strome od x k y (beží nám program), tak pri rozhodovaní sa, či <math>y_i</math> patrí do B uložíme y_i do množiny u ak patrí a do množiny v ak nepatrí (na začiatku u a v reprezentujú kód prázdnej množiny a postupne sa menia tak, že do príslušných množín pridávame práve rozhodované <math>y_i</math>. Ak v strome na obrázku pôjdeme stále vľavo, tak <math>D_u</math> (množina s indexom u) bude prázdna a <math>D_v</math>bude obsahovať <math>y_0</math> a <math>y_1</math>.
Potom nám platí: <math>P(B, x) = y</math> práve vtedy, keď <math>\exists u, v: <x, y, u, v> \in W \and D_u \subset B \and D_v \subset \overline{B}</math>.
{{TODO|toto som nepochopil, takže je to tu napísané len "ako som to zaznamenal"}}
[[TIN064 Rekurzivní spočetnost#Některé z vlastností|Niekde]] bola veta, že ČRF má rekurzívne spočetný graf a tiež sa hovorilo, že by mala existovať nejaká rekurzívne spočetná podmienka (v našom prípade by mala byť podmienka tá vec, s <x, y, v, u> patriacim do W). A my si z toho vytvoríme rekurzívnu podmienku a to tak, že miesto <math>\exists u, v</math> napíšeme <math>\exists u, v, s</math> a s prehlásime za nejaký počet krokov (a B za rekurzívnu, pretože máme <math>C_B</math>) a tak máme B-rekurzívnu podmienku?). A z toho, že to vieme vyjadriť B-ČRF?).
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 <math>\sigma</math> je začiatkom (prefixom) <math>\tau</math> (značíme <math>\sigma</math> \preceq <math>\tau</math> - \preceq nefunguje?). A ešte sme si povedali, že B a <math>C_B</math> 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 jedničkou (problémy sú s číslami ako 0.1 a 0,01111111..., ktoré sú rovnaké, ale predstavovali by inú množinu) a teda množín, s ktorými budeme pracovať je nespočetne veľa.
