Teória vypočítateľnosti
Lecture notes in English
The English version of some lecture notes and other materials.
- The Hydra game
- The connection between the iterated logarithm and the inverse Ackermann function
- Exercises for most lectures
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 Gödelova veta
- 2020-05-20 Viac Gödelovej vety, druhá veta o rekurzii
Skriptá v slovenčine
- Prehľad histórie vypočítateľnosti
- Počítadlové konečné automaty a registrové stroje
- Gramatikové a prepisovacie modely
- Exotické modely vypočítateľnosti
- Primitívna rekurzia
- Ackermannova funkcia, kódovanie PREC fcií do čísel, univerzálna fcia pre PREC
- Vypočítateľné reálne čísla
- Busy Beaver
- Čiastočne rekurzívne funkcie. Zložitosť rekurzívne vyčísliteľných množín
- Goedelova veta
- Fixed-point combinator v Pythone
- Niektoré dôsledky vety o rekurzii
- Triviálny interpreter pre SUBLEQ (napísaný v Pythone) a program počítajúci 2^100
- Program, ktorý vie vyhodnotiť ľubovoľnú primitívne rekurzívnu funkciu (napísaný v Pythone)
Relevantné linky a materiály inde
- 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
- 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
- Nájdite prvú chybu vo "vedeckom článku"
- Skriptá z Cornellu: Arithmetic representability
- Linka: Aritmetická hierarchia
- 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
© Mišof 2020-. All rights reserved. | Based on a design by TEMPLATED (CC-BY 3.0 Unported).