news rss feed
Lecture notes in English
The English version of lecture notes will appear here as they are prepared. Look below for the older Slovak version of lecture notes.
Videá prednášok v slovenčine
- 2020-04-01 Budovanie aparátu primitívnej rekurzie
- 2020-04-08 Ackermannova funkcia
- 2020-04-15 Univerzálna PREC funkcia, Busy Beaver
- 2020-04-29 Čiastočne rekurzívne funkcie. Many-to-one a Turingova redukcia.
- 2020-05-06 Nerozhodnuteľné problémy súvisiace s č.r.f., jednoduché množiny.
- 2020-05-13 Goedelova veta
- 2020-05-20 Viac Goedelovej vety, druhá veta o rekurzii
Skriptá v slovenčine
- skriptá: Prehľad histórie vypočítateľnosti.
- skriptá: Počítadlové konečné automaty a registrové stroje.
- skriptá: Gramatikové a prepisovacie modely.
- skriptá: Exotické modely vypočítateľnosti.
- skriptá: Primitívna rekurzia (UPDATED).
- skriptá: Ackermannova funkcia, kódovanie PREC fcií do čísel, univerzálna fcia pre PREC.
- skriptá: Vypočítateľné reálne čísla.
- skriptá: Busy Beaver.
- skriptá: Čiastočne rekurzívne funkcie. Zložitosť rekurzívne vyčísliteľných množín..
- skriptá: Goedelova veta.
- skriptá: Fixed-point combinator v Pythone.
- skriptá: Niektoré dôsledky vety o rekurzii.
- cvičenia: neforemná zbierka cvičení.
- Triviálny interpreter pre SUBLEQ (napísaný v Pythone) a program počítajúci 2^100.
- Langtonov mravec (video)
- Linka: Slajdy ku aperiodickým dláždeniam
- Hydra: applet kde sa dá hrať a stránka s pravidlami a dôkazom konečnosti.
- Union-find: výskyt inverznej Ackermannovej fcie v praxi
- Linka: Ackermann's Function Is Not Primitive Recursive
- Program, ktorý vie vyhodnotiť ľubovoľnú primitívne rekurzívnu funkciu (napísaný v Pythone)
- Súvis medzi PREC a modernými programami: zo Zemčovej bakalárky úsek tak po stranu 22.
- Stačí jeden while-cyklus: zo Zemčovej bakalárky úsek od strany 28 ďalej.
- Logical pinpointing: problémy s definíciou N v prvorádovej logike
- cvičenia: nájdite prvú chybu vo "vedeckom článku".
- Skriptá z Cornellu: Arithmetic representability
- Linka: Aritmetická hierarchia.
Obsah jednotlivých prednášok
(Tu sa bude ku každej prednáške zjavovať zoznam vecí, o ktorých sa hovorilo.)
Materiály z iných končín sveta
Existuje kopa iných materiálov. Všetky majú spoločnú vlastnosť: Obsahujú aj niektoré veci, ktoré robiť nebudeme, a neobsahujú niektoré veci, ktoré robiť budeme.
Počet hviezdičiek pred názvom materiálu znázorňuje môj subjektívny názor na jeho relevanciu. (Pozor, relevancia nie je kvalita, zaujímavosť ani prístupnosť.)
Johančiny Pohádky z vyčíslitelnosti (originál zakapal, viď kópia
@archive.org).
- Kniha: Hofstadter, Douglas: Gödel, Escher, Bach – An Eternal Golden Braid
Intro z Princetonu k témam Computability a Intractability
- Kniha: Bukovský, Lev: Algoritmicky neriešiteľné problémy
- Kniha: Zlatoš, Pavol: Ani matematika si nemôže byť istá sama sebou
- Bakalárka: Zeman, Marek: Súvis rekurzívnych funkcií a programovacích jazykov
- Esej: Aaronson, Scott: Who Can Name the Bigger Number?
- Kniha: Sipser, Michael: Introduction to the Theory of Computation
- Lecture notes: Trevisan, Luca: Notes on unprovable statements
- Lecture notes: Smith, James T.: Goedel and Tarski
- Esej: Goodman-Strauss, Chaim: Can't Decide? Undecide!
- Micove poznámky z vypočítateľnosti
- Korcove skriptá k vypočítateľnosti (prístupné len z FMFI UK)
- Kniha: Kozen, Dexter: Theory of Computation
- Lecture notes/Handout: Busy beaver.
- Accidentally Turing Complete (obzvlášť MtG! :) )
- Materiály z českého MFF UK: wiki skriptá a poznámky rôznych ľudí (Ladislav Strojil, Martin Trčka, Lenka Novotná)
- Mišofove skriptá z Foje (kapitoly 5 až 7)
- Mišofove poznámky ku Gödelovej vete
- Úvodná stránka Computability theory na Wikipédii
- "Konkurenčné" materiály: skriptá od Vodu, skriptá od Komaru a Vodu, študijné materiály
- Malá ale netriviálna inštancia PKP
- Kniha: Smullyan, Raymond M.: To Mock a Mockingbird (obzvlášť druhá časť knihy)
- Kniha: Švejdar, Vítězslav: Logika – neúplnost, složitost a nutnost
- Gödelov ontologický dôkaz: zaujímavý pokus formálne dokázať existenciu Boha.
- Komiks: Ada Lovelace: The Origin
- Komiks: XKCD
- Komiks: PhD Comics
- Obrázok na pozadí: dôkaz že Conwayova Game of Life je Turing complete. Video: Simulácia Game of Life v nej samej.
- Motivačný príklad jednej prirýchlo rastúcej nevypočitateľnej funkcie