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

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.

Deliberations

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.

One man's lecture notes on computability theory

Contents

Wikipedia and Stanford Encyclopedia of Philosophy

Theory of Recursive Functions and Effective Computability

Deliberations

Further reading