Melvin's digital garden


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.

Course by Klaus Sutner

Unlimited Register Machines, Gödelization and Universality

Busy beaver

How Alan Turing accidentally invented Software

Building a Turing Machine emulator to explore Turing’s great ideas

My heart is a turing machine

Accidentally Turing-Complete

Computational complexity

Jules Richard’s 1905 Paradox of definable numbers may have inspired Turing to write his 1936 paper, see Millican2020.

Links to this note