19 - Parciální rekurzivní funkce
pátek 13. května 2016
10:30
[link] 
Pojmy
Hierarchie funkcí
Všechny funkce
Vyčíslitelné funkce (parciální vyčíslitelné)
μ-rekurzivní funkce (totální vyčíslitelné)
Primitivně rekurzivní funkce
Počáteční funkce
Funkce
Funkce
jako funkci budeme označovat zobrazení:
Definována pro celý definiční obor.
Například +:
𝑝𝑙𝑢𝑠𝑥,𝑦=𝑥+𝑦
Nemusí být definována pro celý definiční obor (ale může).
Striktně parciální funkce
Není definována pro celý definiční obor.
Příklad /:
Nemůžeme dělit nulou.
Počáteční funkce
Hiearchie vyčíslitelných funkcí je založena na dostatečně elementárních tzv. počátečních funkcích, které tvoří „stavební kameny“ vyšších funkcí.
Nulová funkce
(ksí) zobrazuje prázdnou n-tici na 0
𝝃()=𝟎
Funkce následníka 𝜎:ℕ→ℕ
(sigma) zobrazuje číslo na číslo o 1 větší
(pí) vybírá k-tou složku z n-tice
např. 𝜋23(7,6,4)=6, speciální případ 𝜋03(7,6,4)=()
Primitivně rekurzivní funkce
Primitivně rekurzivní funkce jsou funkce tvořené z počátečních funkcí kombinací, kompozicí a primitivní rekurzí
Každá primitivně rekurzivní funkce je totální funkce
Většina prakticky použitelných funkcí v současných počítačích jsou primitivně rekurzivní funkce.
Kombinace f:ℕ𝐤→ℕm a g:ℕ𝐤→ℕn
Výsledek je zřetězení výsledků 𝒇 a 𝒈.
Konvence: n-tici 𝑥1, 𝑥2, …, 𝑥𝑛∈𝑁 budeme oznacovat jako 𝒙.
Příklad: 𝜋13×𝜋334,12,8=(4,8)
Kompozice f:ℕk→ℕm a g:ℕm→ℕn
Provede funkci 𝑓 a výsledek dá na vstup funkci 𝑔.
𝑔∘𝑓, čteme jako "g po f".
Příklad: 𝜎∘𝜉()=1, 𝜎∘𝜎∘𝜉()=2
Primitivní rekurze
𝑓𝑥,0=𝑔𝑥 (𝑔 definuje konec rekurze pro hloubku 0)
Příklady parciálně rekurzivních funkcí
------------------
Parciálně rekurzivní funkce
Parciálně rekurzivní funkce je funkce, kterou lze vytvořit z primitivně rekurzivních funkcí a minimalizace.
Každá parciální rekurzivní funkce je Turingovsky vyčíslitelná.
Každý TS lze převést na parciálně rekurzivní funkci.
Operátorem minimalizace se ParcRecFunc liší od PimRecFunc - zavádí totiž do výpočtu funkce potenciálně nekonečný cyklus.
Minimalizace
Najde nejmenší 𝑦 pro které 𝑔 vrací 0 a všechny nižší hodnoty 𝑦 mají definované výsledky v 𝑔.
Pomocí techniky minimalizace vytvoříme funkci 𝑓:ℕ𝑛→ℕ na základě jiné funkce funkce 𝑔:ℕ𝑛+1→ℕ, tak že definujeme 𝑓𝑥 jako nejmenší hodnotu 𝑦 z ℕ, pro kterou 𝑔𝑥,𝑦=0 a zároveň 𝑔(𝑥,𝑧) je definována pro všechna nezáporná cená čísla menší než 𝑦.
𝑔𝑥,𝑦=0
𝑔(𝑥,𝑧) je definována pro ∀𝑧<𝑦,𝑧∈ℕ
Notace: 𝒇𝒙=𝝁𝒚𝒈𝒙,𝒚=𝟎
Intuitivně: minimalizace vyledává
Začíná hledat od 0 a pokračuje nahoru.
Hledá nejmenší argument, který způsobí, že funkce g vrátí nulu.
Pokud takový argument neexistuje, tak hledání nikdy neskončí.
Tedy výpočet hodnoty 𝑓𝑥 zahrnuje výpočet 𝑔𝑥,0, 𝑔𝑥,1,… a to tak dlouho, dokud nedostaneme:
a)
𝑔𝑥,𝑦=0 
𝑓𝑥=𝑦
b)
𝑔𝑥,𝑧 je nedefinováno
𝑓𝑥 je nedefinováno
Příklad minimalizace
---------------------------------------------
Primitivně rekurzivní funkce si můžeme představit jako: 𝐟𝐨𝐫 𝐢=.. 𝐭𝐨..
Parciálně rekurzivní funkce jsou poté podobné: 𝐰𝐡𝐢𝐥𝐞..
Notes
1. Otazka (předmět) (okruh): Parcialni rekurzivni funkce (TIN)
Kdo me primarne zkousel: Rysavy (jen on)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Pocatecni funkce (vypsat na tabuly, napsala jsem i definicni obor -> obor hodno), kombinace, kompozice, primitivni rekurze - od te me presmeroval dal, ani jsem to nenapsala na tabuli, dost mi to trvalo, chtel se jeste dostat k minimalicaci. Tam jsem si uplne nemohla vzpomenout na ten zapis (na tvar v te | | zavorce), nakonec poradil a zeptal se na dukaz, (pry obecne), ze to ma stejnou vypocetni silu jak TS, tam jsem akorat rekla sestrojeni TS, ale konkretne jsem si nevzpomnela, kdyz na to tedka koukam do slajdu, tak uz je mi to jasny, ale nejak to nenaskocilo. No kazdopadne to uz bylo po zazvoneni budiku, tak rekl, ze mu to staci. Nakonec za B.
From <[link]> 
1. Otazka : Parciální rekurzivní funkce
Kdo me primarne zkousel: Kolář Dušan, doc. Dr. Ing.
V podstatě jednoduchá otázka. Řekl jsem všechny funkce, z kterých se to skládá (prakticky jen vyjmenoval) a pak jsem měl vysvětlit minimalizaci. Tam jsem byl ale slabší a skládal to dohromady z náhodných informací jak puzzle. Bohužel se mi ale některé důležité dílky poztrácely. Především to, jaké má ta minimalizace vstupy a výstupy. Kolář byl moc hodný a hodně pomáhal. Především naznačoval co není pravda ("to mi tam radši ani nepište"), takže to ze mě nakonec asi nějak vytáhl. 
From <[link]> 
70 (Hruška, Vojnar, Herout, Hrubý, Rychlý, Španěl)
1. Otazka (okruh): Parciální rekurzivní funkce
Kdo me primarne zkousel: Hrubý
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Nezačal jsem zrovna nejlíp, tak se radši hned začal ptát. Chtěl popsat počáteční funkce, jejich skládání a minimalizaci plus nějaký základní pojmy. Trošku jsem se v tom motal, ale více méně jsem na všechno nakonec odpověděl.
From <[link]> 
1. Otazka (okruh): Parcialni rekurzivni funkce
Kdo me primarne zkousel: Ceska
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Nejdriv jsem rekl, co to jsou vycislitelne funkce, pak jsem zacal pocatecni a pokracoval na primitivne rekurzivni (u kterych jsem si skoro nezvpomnel na nazev). Ceska moc nechtel formalni zapisy, zajimalo ho spis, jestli rozumim, o cem to je. Nakonec me nechal napsat a vysvetlit vzorec pro minimalizaci.
From <[link]> 
1. Otazka (okruh): 38. Parciální rekurzivní funkce.
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Toto téma jsem měl celkem probrané, takže jsem si věřil, že to nějak uplácám. Nervozita a moje paměť, ale pravidelně vynechávají některá slova v názvech (takže jsem používal stabilně pouze označení "rekurzivní funkce", "parciální funkce" apod.), ale na doplňující otázku jsem reagoval správně. V podstatě stačilo nakreslit hierarchii funkcí a ke každé řéct co ji utváří. Na tabuli chtěl napsat definici minimalizace, protože slovně jsem se do toho zamotával. Po zazvonění budíku byl prakticky konec, žádné natahování. C
From <[link]> 
1. Otázka (okruh): Parciálně rekurzivní funkce (TIN)
Kdo mě primárně zkoušel: Janoušek
Co jsem k tomu řekl(a)/na co se ptali/co mně vytkli:
Šel jsem na to od počátečních funkcí (které jsem vyjmenoval), přes funkce primitivně rekurzivní (taky jsem vyjmenoval), pak jsem zmínil existenci mí-rekurzivních funkcí (tam jsem řekl něco o Ackermanovi a stromové rekurzi), no a nakonec jsem se dostal k parciálně rekurzivním funkcím, kde jsem mluvil o minimalizaci. Zejména minimalizace je zajímala asi nejvíc. Chtěl jsem psát algoritmus v C, ale řekli, že stačí slovy.
Kde jsem trošku zaváhal bylo, že jsem si nebyl úplně jistý, kdy minimalizační funkce skončí (samozřejmě jsem jim řekl, že skončí, když ta vnitřní funkce s danými parametry bude vracet nulu, ale chtěli ještě slyšet, že minimalizační funkce skončí i tehdy, když není pro dané hodnoty parametrů vnitřní funkce definována... tzn. např. když tam někde dostanete třeba dělení nulou).
Pak ještě chtěli vědět, kam až sahají totální funkce, načež jsem ukázal někam k těm mí-rekurzivním. Chtěli také vědět, jestli je Ackermanova funkce totální (řekl jsem ano a bylo to správně).
Janoušek byl hodný, vstupoval do toho trošku i Češka (zejména když už se Janoušek nadechoval k tomu, že se mě zeptá na důkaz ekvivalence parciálně rekurzivních funkcí a Turingových strojů - což bych uznávám nevěděl, řekl bych, že to Češka z mého kyselého obličeje čul a tak radši zavedl řeč na něco jednoduššího).
From <[link]> 