Syntax highlighting of Archiv/TIN065 Prednáška 01

{{TIN065 Prednášky}}
Na vyčísliteľnosti I sme mali 1-prevoditeľnosť: <math>A\leq_1 B</math> znamená, že existuje prostá ORF funkcia f, pre ktorú platí, že <math>a \in A \Leftrightarrow f(a) \in B</math>.
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á (<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 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===
<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) = true \leftrightarrow x \in A \leftrightarrow \alpha(C_B(y_1),C_B(y_2), \cdots, C_B(y_n)) = true</math>, kde <math>C_A</math> je charakteristická funkcia <math>A</math> a <math>C_B</math> je charakteristická funkcia <math>B</math>. (Spomínaná ORF teda priradí každému <math>x</math> kód funkcie <math>\alpha</math> a hodnoty 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 nezá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 <math>K</math> 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 "Je <math>y</math> prvkom <math>B</math>?". 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: <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.

===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 strom.PNG]]

Tento strom zachytáva všetky možné scenáre behu programu pre ľubovoľný vstup <math>x</math> a ľubovoľnú množinu <math>B</math>. Program dostane na vstupe <math>x</math> a množinu <math>B</math>. 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é <math>y_i</math> prvkom množiny <math>B</math>. 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 <math>W</math>, ktorá obsahuje štvorice <math><x, y, u, v></math>, kde <math>x</math> je vstup programu, <math>y</math> je jeho výstup a <math>u</math> a <math>v</math> sú indexy konečných množín, ktoré vyrobíme tak, že keď ideme po vetve v strome od <math>x</math> k <math>y</math> (beží nám program), tak pri rozhodovaní sa, či <math>y_i</math> je prvkom množiny <math>B</math> uložíme <math>y_i</math> do množiny <math>u</math> ak <math>y_i</math> je prvkom množiny <math>B</math> a ak <math>y_i</math> nie je prvkom množiny <math>B</math>, tak <math>y_i</math> uložíme do množiny <math>v</math>. Množiny <math>u</math> a <math>v</math> na začiatku reprezentujú kód prázdnej množiny a postupne sa menia tak, že do nich pridávame práve rozhodované <math>y_i</math> podľa príslušnosti do <math>B</math>. Ak v strome na obrázku pôjdeme stále vľavo, tak <math>D_u</math> (množina s indexom <math>u</math>) bude prázdna a <math>D_v</math> bude obsahovať <math>y_0</math> a <math>y_1</math>.

Potom 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|Nasledujúci odstavec 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čí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 <math><x, y, v, u></math>, ktoré je prvkom <math>W</math>). A my si z toho vytvoríme rekurzívnu podmienku tak, že miesto <math>\exists u, v</math> napíšeme <math>\exists u, v, s</math> a <math>s</math> prehlásime za nejaký počet krokov (a <math>B</math> za rekurzívnu, pretože máme <math>C_B</math>) a tak máme <math>B</math>-rekurzívnu podmienku. A z toho, že to vieme takto vyjadriť je funkcia <math>\Phi_{z, s}^{B}</math> 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 <math>\sigma</math> je začiatkom (prefixom) <math>\tau</math> (značíme <math>\sigma</math> <code>\preceq</code> <math>\tau</math>). A ešte sme si povedali, že <math>B</math> 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 jednotkou. Problémy sú s číslami ako <math>0.1</math> a <math>0,01111111...</math>, ktoré sú rovnaké, ale predstavovali by inú množinu. A teda množín, s ktorými budeme pracovať, je nespočítateľne veľa.