Article series6 parts135 min read

Intro to incompleteness

A computational approach to Gödel’s First Incompleteness Theorem, using Python programs and Turing machines.

This series is largely based on the work in this project, which is largely based on:

MacCormick, J. (2018). What Can Be Computed?: A Practical Guide to the Theory of Computation. Princeton University Press. https://doi.org/10.1515/9781400889846
Aaronson, S. (2017). Rosser’s Theorem via Turing machines. https://scottaaronson.blog/?p=710
Sipser, M. (2012). Introduction to the Theory of Computation (3.ª ed.). Cengage Learning.

Chapters

A question about truth
From Aristotle to Turing — the road to incompleteness.
6 July 20266 min read
Python is a Turing machine
Proving that Python programs and Turing machines are computationally equivalent.
13 July 202644 min read
The program that cannot exist
Some problems cannot be solved by any program — and we can prove it.
20 July 202632 min read
Proof is not the same as truth
Formalising proof and truth — and discovering their limitations.
27 July 202633 min read
A truth that cannot be proved
Every sufficiently powerful formal system contains truths it cannot prove.
3 August 202617 min read
What incompleteness actually says
A computational proof that arithmetic cannot be both complete and mechanical.
10 August 20263 min read