{{TIN065 Prednášky}}
Na vyčísliteľnosti I sme mali 1-prevoditeľnosť:
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á (
Truth table reducibility
Priradenie funkcie
K tomuto môžeme vymyslieť nejaké obmedzenia, či už na
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
Neformálne:
Keďže hovoríme o programe, zišiel by sa programovací jazyk. Prvá možnosť je použiť
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
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
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
Potom platí:
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
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 \preceq