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