(This is Yan Sheng.) $\newcommand{\bb}{\mathbb}\newcommand{\Con}{\operatorname{Con}}$I once read this mind-bending blog post by Joel David Hamkins that proves this result: Theorem : There is a Turing machine program $P$ such that for any function $f:\bb N\to\bb N$, there is a model of Peano arithmetic in which $P$ computes $f$ on the standard natural numbers. Read that again: there is a single Turing machine that outputs any given function—even uncomputable ones (!!)—if you run it in the correct universe. If this statement doesn’t surprise you, I’m not sure what else would (unless you work in logic or set theory; I’m convinced that those people routinely believe as many as six impossible things before breakfast ). A extraordinary claim needs an extraordinary proof, and when I read through Hamkins’s argument I came across a lesser absurdity: a theory that proves its own inconsistency. Since all my knowledge of formal logic is from folklore, this post is my attempt to informal...
