{{TIN064 Skripta}} __NOTOC__ ## Účel ## Tento text měl původně za cíl usnadnit pochopení předmětu [Vyčíslitelnost I](Vyčíslitelnost%20I) těm, kteří vůbec netuší, o čem to je. Dalším cílem bylo doplnit (alespoň částečně) [Strojilova skripta](TIN064%20Skripta%20Ladislava%20Strojila), 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](http://atrey.karlin.mff.cuni.cz/%7Ejohanka/vyuka/pohadky_vycislitelnost.html), 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í](Aleš%20Pultr)" :-), 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](User: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 ---- * [Motivace](http://abstrusegoose.com/244)