# 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:
Luboš Brim's textbook:
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

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.

## 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.