Tag Archives: godel’s first incompleteness theorem

Consequences of the Halting Problem: Gödel’s First Incompleteness Theorem

In my first post on this blog, I defined and proved my favorite fact: The halting problem is undecidable. You should probably read that post if you don’t know what that means, but in brief, it means that it is impossible to write a computer program that will always correctly tell you whether any given computer program will run forever or eventually stop.

I promised to talk about some of the far-reaching consequences of this fact in future posts, and here I am keeping my promise, if a little late. (Don’t get used to me keeping my promises on this blog, though…) I’ll start with arguably the biggest consequence of the halting problem’s undecidability: Gödel’s First Incompleteness Theorem.

As is my m.o., I’ll try to keep the discussion accessible to laypeople; I’ll provide lots of context; and I’ll just generally be extremely long-winded.

This post will be even more long-winded than usual because I feel the need to provide way too much context. To sort of acknowledge that this post is absurdly long, I’ve put a little (*) in the heading of sections that are less tangential. I’m incredibly biased, of course, but I suggest attempting to make it through the whole thing, and if you get tired somewhere around Euclid or Cantor, skip ahead to the next asterisk.

Continue reading