One man's lecture notes on computability theory

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:

• FI:IA046 Vyčíslitelnost - Informace o předmětu

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:

• FI:IB107 Vyčíslitelnost a složitost - Informace o předmětu

Wikipedia and Stanford Encyclopedia of Philosophy

Top Wikipedia articles/pages:

• W: Computability theory
• W: Category: Computability theory

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:

• W:Decidability (logic)
• W:List of undecidable problems

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

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.

Further reading

• 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