TIN064 Generování RSM
| Wiki-skripta pro Vyčíslitelnost I |
| Obsah |
|---|
|
Funkce $ f $ je úseková, je-li jejím definičním oborem "počáteční úsek" $ \mathbb{N} $ (nebo celé $ \mathbb{N} $). Tedy když je definovaná pro "prvních $ k $ čísel". Všimněme si, že PRF a ORF jsou vždycky úsekové (jsou totiž totální), zatímco ČRF jsou samozřejmě úsekové jen některé.
Nápad na formalismus: pro úsekovou f platí: $ \forall k: f(k)\uparrow \Rightarrow \forall j>k: f(j)\uparrow $ (XXX je f s prázdným def. oborem úseková?)
Ukazuje se, že na některé věci nepotřebujeme totální funkce a stačí nám pouze úsekovost. Konkrétně umíme pěknými úsekovými ČRF efektivně spočítat všechny množiny rekurzivní (prostá a rostoucí ČRF) a rekurzivně spočetné (prostá ČRF).
Generátory RM[editovat | editovat zdroj]
Věta: Rekurzivní množiny jsou právě obory hodnot rostoucích úsekových ČRF.
Důkaz: Klasický ekvivalenční, každou implikaci dokážeme zvlášť.
- Máme rekurzivní $ M $, potřebujeme najít rostoucí úsekovou $ f $ aby $ M = rng(f) $
- Pro M existuje charakteristická ORF g: $ g(x)=1 \Leftrightarrow x\in M $. Hledaná f(x) zkusí spočítat g(0), g(1), g(2) ... dokud nedostane 1. Jakmile g(k)=1, k je nejmenší prvek M. Ten lze přeskočit a hledat dál druhý, třetí, čtvrtý nejmenší. f(0) vrátí nejmenší prvek M, f(1) vrátí druhý nejmenší atd. f je rostoucí a úseková ČRF.
- Formálně: $ f(0) = \mu_x (x \in M) $, $ f(k+1) = \mu_y (y > f(k) | y \in M) $
- Máme $ f $, je $ M=rng(f) $ rekurzivní? Musíme umět u $ f(x)=y $ snadno (bez minimalizace) najít pro každé $ y $ odpovídající $ x $.
- Pokud $ f $ není totální, má konečný definiční obor a jde to omezeným forcyklem (primitivní rekurzí).
- Ivan: podle mě stačí říct, že když úseková f není totální, její obor hodnot je konečný a konečné množiny jsou rekurzivní (zkontroluju přítomnost vstupu v konečném poli a vrátím 0/1).
- Pokud $ f $ je totální, využijeme úsekovosti a monotónnosti - nutně $ x \le y $, jinak jsme museli nějaké $ x $ přeskočit (spor s úsekovostí) nebo prohodit (spor s růstem). Zase nám stačí primitivní rekurze, strčíme jí $ y $.
- Ivan: pro dané y máme vždy umět rozhodnout, zda je v oboru hodnot f. Začneme počítat f(0), f(1), ... a když dostaneme hodnotu y - vrátíme 1. Pokud hodnota překoná y bez nalezení y, vrátíme 0. Popsaná funkce je ORF, charakteristická pro množinu M, tedy M je rekurzivní.
- Pozor! Jestli je $ f $ totální nemusíme umět efektivně zjistit.
- Pokud $ f $ není totální, má konečný definiční obor a jde to omezeným forcyklem (primitivní rekurzí).
JM: No jsem z toho ponekud zmateny. Jake ma to ze to neumime efektivne dusledky? Jde-li jen o existencni dukaz, tak je to ok; nicmene typicky chceme takovouhle vetu pouzit jako "mam rostouci usekovou CRF $ f $ co generuje rekurzivni $ M $; dostanu prvek $ a $ a mam zjistit je li z $ M $". No a jak to krucinal udelam, kdyz nevim jestli je ta CRF totalni a kdyz to budu zjistovat me muze minimalizace nakrasne zavest kamsi. Znamena ta veta snad to, ze kazdy kdo ji chce takhle pouzit musi navic bud dokazat, ze je totalni, nebo dodat velikost "konecneho definicniho oboru $ f $". Chapu to spravne? A jestli ano, nemelo by se to zduraznit? A pouzivame to v dalsich kapitolach skutecne tak?
RK: no ja som to pochopil tak ze je to existencny dokaz a to "pozor!" hovori prave o tom, ze to takym sposobom ako pises nemozes pouzit. Jednoducho, obor hodnot f je rekurzivna mnozina, ale to este neznamena ze ju vies efektivne nalezt (resp. nalezt nej charakteristicku funkciu)... keby si vedel efektivne nalezt obor hodnot nejakej CRF (na to potrebujes def. obor, inak sa zacyklis), uz by to nebola CRF
PB: Ja si myslim, ze jsem to tam napsal tehdy trochu nestastne - brani nam neco v oblibenem triku pustit obe vetve paralelne? Nevidim problem v urceni, zda je funkce totalni, ale pokud f neni totalni, zjistit, kde postavit zarazku; v tu chvili o te funkci musime vyvestit, jak se chova, a to asi v obecnem pripade udelat nemuzeme. Ale vime, ze nejakou zarazku mit musi, jen nevime, jake konecne cislo uz je dost velke, aby tu zarazku dohnalo.
JT: Paralelni pusteni obou vetvi imho nepomuze. Predstav si situaci, ze uz jsi prozkoumal hodnoty 0..y (tj. vetev pro totalni f) a x jsi nenasel. Tak nevis nic. Bud tam y nepatri, nebo f neni totalni.
MD: Konzultovali jsme to s doc.Kucerou. Neni to konstruktivni dukaz ale dukaz "neefektivne existencialni". Opravdu pocita s jednou kapkou vsevedoucnosti, ktera nam rekne, zda je mnozina totalni nebo ne. Zbytek je skutecne efektivni. Argument JT je platny.
Věta: (Strojil) Nekonečné rekurzivní množiny jsou právě obory hodnot rostoucích ORF.
Důkaz: Žádná věda, snadno plyne z předchozí věty!
- Pomněte, že ORF je úseková ČRF a lze snadno (z prostoty funkcí) nahlédnout, že ČRF s konečným úsekem generují konečné rekurzivní množiny, zatímco ČRF s nekonečným úsekem (tedy totální, tedy ORF) musejí generovat ty nekonečné.
Věta: (Lenka) Nekonečné rekurzivně spočetné množiny jsou právě obory hodnot prostých ORF.
Důkaz: Obdobně plyne naopak z následující věty.
Generátory RSM[editovat | editovat zdroj]
Věta: Rekurzivně spočetné množiny jsou právě obory hodnot prostých úsekových ČRF.
- Rostoucí ČRF byla také prostá, takže jsme jen podmínku zmírnili - a dostali tak širší sadu množin.
Důkaz: Zase dvě implikace, druhá možná maličko náročnější.
- Máme ČRF $ f $. Již dříve jsme ukazovali větu, že obor hodnot každé ČRF je RSM.
- Máme RSM $ M $, dle definice RSM existuje $ \varphi(x) $: $ M = dom(\varphi) $.
- Chce to Cimrmanův krok stranou - vyrobit si z $ \varphi $ množinu $ B=\{(x,s)|\varphi(x)\downarrow\mbox{po s krocich}\} $.
- Připomínka formálního zápisu: $ T_1(\varphi,x,s) \land \forall p<s: \neg T_1(\varphi,x,p) $
- To je evidentně rekurzivní množina, proto jak jsme si právě dokázali, má generátor $ h $ - rostoucí úsekovou ČRF (s oborem hodnot B).
- $ f(y) = h(y)_1 $ - vezmeme pár s daným číslem a vydělíme z něj $ x $, což je vstup, pro který $ \varphi(x)\downarrow $ po nějakém počtu kroků. $ f $ je zjevně stejně úsekové jako $ h $, a sice již není rostoucí, ale stále je prosté (f(y)=f(z)=x by znamenalo, že $ \varphi(x)\downarrow $, což vždy dá stejný počet kroků, tedy y=z) a pokrývá celou RSM - každé $ x $ bylo evidentně právě v jednom páru v B.
- Chce to Cimrmanův krok stranou - vyrobit si z $ \varphi $ množinu $ B=\{(x,s)|\varphi(x)\downarrow\mbox{po s krocich}\} $.
Embedování RM v RSM[editovat | editovat zdroj]
Důsledek: Každá nekonečná RSM $ M $ obsahuje nekonečnou rekurzivní podmnožinu.
Důkaz:
- RSM $ M $ je nekonečná, tedy jak jsme si před chvílí dokázali existuje prostá ORF $ f $, která ji generuje.
- V RSM $ M $ najdeme rostoucí podposloupnost (to umíme, protože generátor $ f $ je ORF)
- $ g(0) = f(0) $
- $ g(k+1) = f(\mu_j(f(j) > g(k)) $
- $ g $ je rostoucí úseková ORF, tedy její obor hodnot je nekonečná rekurzivní množina, ta je zároveň evidentně podmnožinou $ M $. Co víc si v životě přát?
