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. Oops! I stand corrected. Thanks for the reply!

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s