halting-problem.py

### PROOF THAT YOU CANT PROVE EVERYTHING ###

# 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):
    pass
  return True

contradiction(contradiction) # What will happen!?