One man's lecture notes on computability theory
 |
This resource includes primary and/or secondary research. Learn more about original research at Wikiversity. |
What follows are intended to be Dan Polansky's lecture notes on computability theory, also known as recursion theory. They are published in the hope that they may be helpful for someone else as well as a learning resource.
The initial plan to create a minimum functional artifact is to start with Luboš Brim's (who teaches computability) syllabus for computability theory course and create a set of links to relevant Wikipedia articles. Thus, one would learn by studying the Wikipedia articles one at a time. The plan is to then expand this page with lecture notes proper, but with the view that the purpose is not to duplicate Wikipedia; and thus, it would perhaps be in a bullet-point based outline-like matter; let us see.
One aim is to link to excellent freely available lecture notes online.
Luboš Brim's syllablus/course outline in Czech:
Luboš Brim's textbook:
- Vyčíslitelnost, fi.muni.cz -- available only within muni.cz domain (one would wish this was publicly available; one cannot earn so much money from that kind of textbook useful only for Czechs anyway, can one?)
Jan Strejček's syllablus/course outline in Czech on a course preceding the above one, providing a mere introduction and combining it with computational complexity theory:
Wikipedia and Stanford Encyclopedia of Philosophy
[edit | edit source]Top Wikipedia articles/pages:
Wikipedia articles choice of which is based on Luboš Brim's syllabus/course outline, with an extension from Jan Strejček's outline:
Preliminary course (Strejček)
- W: Church–Turing thesis
- W: Undecidable problem
- W: Computable function
- Partially decidable problem: see W: Recursively enumerable language
Advanced course (Brim):
- W: Rice's theorem
- W: Recursive language
- W: Recursively enumerable language (see also W:Computably enumerable set)
- W: Creative and productive sets
- W: Simple set (also covers immune set)
- W: Kleene's recursion theorem (AKA Rogers's fixed-point theorem)
- W: Arithmetical hierarchy (Kleene–Mostowski hierarchy)
- W: Gödel's incompleteness theorems
- W: Oracle machine
- W: Analytical hierarchy
- W: Post correspondence problem
Other related Wikipedia articles:
Relating Stanford Encyclopedia of Philosophy (SEP) articles:
- Computability and Complexity
- Recursive functions
- The Church-Turing Thesis
- Gödel’s Incompleteness Theorems
Theory of Recursive Functions and Effective Computability
[edit | edit source]Luboš Brim's course seems to be based on the book Theory of Recursive Functions and Effective Computability, captured in Wikidata. As per zbmath.org, the book syllabus is this: Recursive Functions. Unsolvable Problems. Purposes; Summary. Recursive Invariance. Recursive and Recursively Enumerable Sets. Reducibilities. One-one Reducibility: Many-one Reducibility; Creative Sets. Truth-table Reducibilities: Simple Sets. Turing Reducibility: Hypersimple Sets. Post's Problem; Incomplete Sets. The Recursion Theorem. Recursively Enumerable Sets as Lattice. Degrees of Unsolvability. The Arithmetical Hierarchy (Part I). Arithmetical Hierarchy (Part II). The Analytical Hierarchy.
Deliberations
[edit | edit source]This section is for relating deliberations, possibly half-original ones.
The computability theory should perhaps better be called incomputability theory. Since, it first slices functions from N to N into computable and incomputable. But then, it realizes that among those that are incomputable, some are more so. This sounds like some kind of linguistic pun, but it is meant in earnest. Since, the set of incomputable functions is then sliced into those that are simple (technical term) and those that are not and the arithmetic hierarchy introduces another structure.
One can ask whether the computability theory is really a part of the computer science or rather of the logic, as some sources indicate. Since, the theory has little to do with practical computing, given it drives its attention toward the finer structure of the space of incomputables. By contrast, the so-called complexity theory (arguably a misnomer) shows that some functions are more easily computable than others, so are in a sense more computable.
Further reading
[edit | edit source]- Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987. ISBN 0262680521 -- this is indicated by Luboš Brim as a possible course reading
- Theory of recursive functions and effective computability by Rogers, H. (Hartley), 1967, archive.org -- access restricted; also at Wikidata
- Automata, Computability, and Complexity, ocw.mit.edu -- rather different in scope
- Theory of Computation, ocw.mit.edu -- rather different in scope, including complexity theory
- Lecture notes -- various lecture notes in computer science, some in English and some in Czech, ktiml.mff.cuni.cz
- Vyčíslitelnost, lecture notes from lectures by Antonín Kučera, compiled by Ladislav Strojil, in Czech, ktiml.mff.cuni.cz
- Vyčíslitelnost, lecture notes from lectures by Antonín Kučera, compiled by Kyrylo Karlov, in Czech, ktiml.mff.cuni.cz
- IN13 Vyčíslitelnost, Státnice na FI MUNI, statnice.dqd.cz, in Czech
- Short Lecture Notes — Computability (2008–2013), disi.unitn.it -- a different scope but there is some overlap
- Theory of Computation- Lecture Notes, michaellevet.github.io -- a very different scope but kind of nice as a refresher on selected topics in computer science
- Course notes for Computability and Complexity, cs.um.edu.mt -- very different scope
- CS 3780: Theory of Computation, summit.plymouth.edu -- very different scope
- Computability and Recursion by Robert I. Soare
- The History and Concept of Computability by Robert I. Soare
- Edmund Weitz video in German (would be excellent): none found
- Computability Theory, Notes(S. Cook and T. Pitassi), cs.toronto.edu/~toni -- computable function, Church's Thesis, recursive and recursively enumerable sets, reducibility, Rice’s theorem, Undecidable combinatorial problems