Simon’s Halting Problem Gist

You can easily turn every statement into a program. If the program stops, or “halts”, then the statement is true, and if it never stops, or “loops”, the statement is false.

Like, for example, the following program corresponds to the statement: “There’s at least one even number that cannot be expressed as the sum of two primes” (this is the negation of the so-called “Goldbach Conjecture”):

So, if we can figure out if any program will halt or not halt, we can prove everything! Can we do that, though?

Read more on Simon’s GitHub

3 Replies to “Simon’s Halting Problem Gist”

      1. openmind123omega's avatar

        Oops! I stand corrected. Thanks for the reply!

        Like

Leave a comment