Computability
The “recursion” in recursion theory actually means computability.
S is recursive/decidable iff there is a program that halts and outputs whether s is in S
S is recursively enumerable iff there is a program that enumerates S or P(s) halts if s in S or runs forever otherwise
The halting set is in RE but not in R. We can enumerate the halting programs but halting is not decidable.
Small undecidable sentences in Peano arithmetic
Smallest TM where halting is uknown
Primitive recursive function is one where we can determine the upper bound of a loop before entering it. Most studied computable functions are primitive recursive.
Unlimited Register Machines, Gödelization and Universality
How Alan Turing accidentally invented Software
Building a Turing Machine emulator to explore Turing’s great ideas
Jules Richard’s 1905 Paradox of definable numbers may have inspired Turing to write his 1936 paper, see Millican2020.