TIN064 wiki-skripta
| Wiki-skripta pro Vyčíslitelnost I |
| Obsah |
|---|
|
Účel[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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
