TIN064 wiki-skripta
| Wiki-skripta pro Vyčíslitelnost I |
| Obsah |
|---|
|
Účel
Tento text měl původně za cíl usnadnit pochopení předmětu Vyčíslitelnost I těm, kteří vůbec netuší, o čem to je. Dalším cílem bylo doplnit (alespoň částečně) Strojilova skripta, která začínají až od Kleeneho věty o normální formě. Později mi přišly i některé další pasáže ve zmíněných skriptech jako příliš stručné, a tak jsem přidal i ty. Nakonec jsem se rozhodl pro formát "wiki-skript" místo původně zamýšleného TeXu, ale pokud se to tady rozroste a opraví chyby atd., tak to třeba někdo převede zase do pdf, aby se to i pěkně četlo.
Upozornění 1
Tento text je částečně inspirován Johančinými pohádkami z vyčíslitelnosti, což se občas projevuje v poněkud odlehčenější formě výkladu. Ze stejného zdroje bych si též dovolil citovat důležité upozornění:
- "Text je zhmotněním mých vlastních pocitů z vyčíslitelnosti, nikde jsem si tyto pocity neověřoval, může tedy být matoucí či dokonce nepravdivý a nikdo vám neslibuje, že má vůbec něco společného s výše jmenovanou přednáškou, že se pomocí něj naučíte na zkoušku, že vás pak Kučera nevyhodí apod."
Upozornění 2
Pokud vám některá z informací v těchto wiki-skriptech přijde "triviálně triviální" :-), tak se nemusíte bát (jako v jiných textech), že vám asi něco uniklo – neuniklo, ani jsem z nikoho nechtěl dělat blbce. Opravdu to je natolik zřejmé, že jsem to asi nemusel zmiňovat. Ale pořád lepší, když něco přebývá, než když to pak někomu chybí.
Prosba
Text je sice místy psán v první osobě, ale doufám, že bude dále doplňován atd. – od toho je to tady na wiki. Pokud nějaké části (důkazu) nerozumíte, nebojte se udělat poznámku přímo do textu: např. vložit šablonu {{TODO|Mohl by mi někdo vysvětlit, proč...}}, případně se víc rozepsat na diskuzní stránce. Jistě nejste sami, komu to není jasné.
--Milvus 16:12, 8 Feb 2008 (CET)
Přehled obtížnosti
Jistě se najde mnoho těch, kteří na první pokus zvesela začnou studovat, projdou prvními dvěmi wiki tématy, dojdou k závěru, že to půjde, vrátí se ke svému oblíbenému seriálu, a noc před zkouškou zažijí ošklivé překvapení. Tohle je - nutně do určité míry subjektivní - přehled "postupu studia":
- Halting problém, další prerekvizity - snadné, mělo by být max. na hodinku až dvě, zejména pro promované bakaláře
- ČRF, ORF, PRF - vydržela-li studijní morálka alespoň na první přednášky, snad také max. hodinka pro ty nejpečlivější
- Kleeneho věta, univ. PRF - pro člověka vyčíslitelnosti neuvyklého první možný konceptuální zádrhel, je třeba si to důkladně rozmyslet, už bude jen přituhovat
- Rekurzivní spočetnost - takový soubor cvičení na Kleenovu větu a low-level aplikaci rekurzivních operátorů, první standardní technické důkazy
- Převeditelnost, generátory - vymizí poslední vtipy, objeví se první masivně abstraktní koncepty, ale stále je to zvládnutelné
- Imunní/simple množiny - pro změnu první z množin, u kterých už ani není moc jasné, k čemu jsou vlastně dobré; když si ale člověk chvíli čmárá na papír tu definici, měla by dojít každému a věta je pak snadná
- Věty o rekurzi - věty o pevných bodech jsou fetišem všech matematiků stavějících si nové systémy a důkazy jsou v každém stejně neintuitivní formální finty; na druhou stranu, dokáže se první, a další (až na Riceho) už je jen to samé dokola
- Produktivní a kreativní množiny - IMHO výrazně nejtěžší partie, ze které je ale při zkoušce pravidelně alespoň jedna otázka; už samotný koncept není snadné pochopit, důkazy jsou hrůzně obsáhlé, složité a technické a materiál může trvat důkladně pochopit řadu hodin
- Neoddělitelné množiny - určitá úleva, důkazy už jsou zase poměrně rozumné, zato pochopit, co vlastně konkrétně taková efektivní neoddělitelnost znamená, není snadné; nezkouší se příliš často, ale je třeba být na tu eventualitu připraven
- Gödelova věta - kvůli tomu celou tu námahu podstupujeme, ovšem finální důkazy jsou tak těžké, že se už ani neprobírají a je to tedy dost hubená kapitolka, navíc se zkouší málokdy
