{{Předmět|Vyčíslitelnost I|Antonín Kučera|TIN064}}
== Probraná látka (2007/2008) ==
* Turingovy stroje - základ, modifikace<span style="color:gray">, univerzální TS</span>
* <span style="color:gray">Základní definice k PRF a ČRF</span>
* <span style="color:gray">Ackermannova funkce</span>
* <span style="color:gray">Ekvivalence TS a ČRF</span>
* <span style="color:gray">Univerzální ČRF</span>
* <span style="color:gray">Rekurzivní spočetnost</span>
* <span style="color:gray">Věty o rekurzi + aplikace</span>
* <span style="color:gray">Dvojice množin</span>
* <span style="color:gray">Gödelovy věty</span>
== Zkouška ==
Kučera na tabuli napsal dvě otázky společné pro všechny (viz níže). Vše chtěl i s důkazem. Čas nebyl omezený, chodil mezi námi a průběžně nás usměrňoval (tedy upozornil, když někdo dokazoval něco jinýho než měl...). Pokud byl spokojen, napsal rovnou známku. Nebo taky řekl, že vidí, že tomu nerozumím, jestli bych si nepřišel příště.
=== Otázky ===
* Ackermanova funkce
* TS <=> ČRF
* Univerzální funkce pro třídu PRF (zda existuje a do jaké třídy patří)
* Věta o selektoru
* Věty o generování rekurzivně spočetných a rekurzivních množin
* Konstrukce prosté (simple) množiny
* věty o rekurzi + aplikace (Rice)
** který program počítá déle, jestli ''a'' nebo ''f(a)'' a jak
* imunní, produktivní a kreativní mn.
* Důkaz, že existuje obecně rekurzivní produktivní funkce
* Vztah kreativnosti a 1-úplnosti (navíc i důkaz lemmatu o vztahu produktivních množin a převoditelnosti z <math>\overline{K}</math>)
* Dokázat, že <math>\overline{K}</math> (doplněk K) je nejjednodužší produktivní množina. Tzn. Všechno co převedu na <math>\overline{K}</math> je produktivní a když je C produktivní, tak ji převedu na <math>\overline{K}</math>. Důkaz byl vlastně totožný s předchozím příkladem z tohoto seznamu.
* Efektivně neoddělitelné množiny (všecho o nich - definice, existence, a ještě dokázat, že ef. neoddělitelnost = 1-úplnost)
* Konstrukce efektivně neoddělitelné množiny
* Godelovy věty (znát definice (ZAS, axiomatizovatelná teorie...) a znění Gödelovy věty)
== Materiály ==
[http://ktiml.mff.cuni.cz/downloads/vycislitelnost.pdf Skripta Ladislava Strojila] toho obsahují daleko víc, než bylo na přednáškách probráno. Na druhou stranu začínají až Kleenovou větou o normální formě bez jakéhokoliv vysvětlování terminologie. Má-li však člověk základy pochopeny odjinud, je to ideální studijní materiál.
Pokud vůbec netušíte o co jde, před tím, než se budete učit formalismy si přečtěte [http://atrey.karlin.mff.cuni.cz/~johanka/vyuka/pohadky_vycislitelnost.html Johančiny pohádky o vyčíslitelnosti], pomůže to získat trochu nadhled.
[http://lucy.troja.mff.cuni.cz/labtf/poznamky/vycislitelnost.zip Zápisky (Martin Trčka)]
Jsou to poznámky za dva semestry Vyčíslitelnosti z let 2001/2002. Nutno ovšem dodat, že látka dnešní Vyčíslitelnosti I končí v těchto poznámkách až někdy v březnu. Důkazy jsou poměrně dobře okomentovány a občas jsou zde zapsány i vtipné výroky z přednášek. Vhodná je kombinace s novějšími zápisky od Lenky Novotné(viz níže).
[http://mff.modry.cz/vycislitelnost/zapisky/Lenka/ Zápisky (Lenka Novotná)], úprava do světlejší tisknutelné podoby 2x2 - [http://beta.arcig.cz/~bernard/lenka.pdf lenka.pdf].
[http://www.ms.mff.cuni.cz/~zajio1am/notes/vycislitelnost_1-tin064-kucera-mixed.tar Zápisky (Eva Ondráčková, Lenka Novotná)].
[http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/vycislitelnost.sxw Poznámky z přednášky].
