Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
# 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"):
def example(): # (assumes a get_primes function, but you get the idea)
n = 4
while True:
primes = get_primes(n)
found = False
for x in primes:
for y in primes:
if x + y == n:
found = True
if found == False:
return True
n += 2
# So, if we can figure out if any program will halt or not halt, we can prove everything! Can we do that, though?
# Spoiler: NO. Here's the proof. I'll give you the program, can you complete the proof from it?
def halts(prog, inp):
# returns True if program prog halts on input inp
# returns False otherwise
def contradiction(prog):
while halts(prog, prog):
return True
contradiction(contradiction) # What will happen!?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment