arXiv:1909.04569cs.LO
In this essay we'll prove Gödel's incompleteness theorems twice. First, we'll prove them the good old-fashioned way. Then we'll repeat the feat in the setting of computation. In the process we'll discover that Gödel's work, rightly viewed, needs to be split into two parts: the transport of computation into the arena of arithmetic on the one hand and the actual incompleteness theorems on the other. After we're done there will be cake.
Linked by 3 identifiable commenters in 3 comments across 3 threads, from Dec 2019 to Jun 2025. Found in 2 HN submissions from Dec 2022 to Apr 2023. Open submission discussions.
"Incompleteness ex Machina" by Sebastian Oberhoff, is a nice paper-length exposition https://arxiv.org/abs/1909.04569.
There's another paper called "Incompleteness Ex Machina" with several proofs of both the first and second incompleteness theorems. https://arxiv.org/abs/1909.04569
Connected through shared HN threads, not inferred similarity or a recommendation.
Yeah, but the vexing part is "how can that be true for e.g. N=643 but not N=642"? What happens at whatever number it starts true at? Incidentally, Gödel's theorem eventually comes down to a halting-like argument as well (well, a diagonal argument). There is a presentation of it…
ajkjkView on HNParent context