CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: The Halting Problem


# The Halting Problem (a 112-friendly version) ############################################################################## # Step 1: run(program, input) ############################################################################## # We start with a function that can run a given program with a given input: # (Students do not need to write the following run function from scratch, # but should understand what it is doing): import io, sys def run(programString, inputString): sys.stdin = io.StringIO(inputString) try: exec(programString, globals()) except Exception as e: print("Error:", e) finally: sys.stdin = sys.__stdin__ # First, let's just run an everyday program: p1 = ''' def fib(n): return 1 if (n < 2) else fib(n-1) + fib(n-2) N = int(input()) print([fib(n) for n in range(N)]) ''' # Example 1.1: Run a program with expected input run(p1,'7') # --> [1, 1, 2, 3, 5, 8, 13] # Example 1.2: Run the same program with itself as input (crashes) run(p1, p1) # --> Error: invalid literal for int() with base 10: '' ############################################################################## # Step 2: run a program with itself as input (without crashing) ############################################################################## # Now let's patch p1 so that it does not crash on non-int input, # so it can run with itself as input: p2 = ''' def fib(n): return 1 if (n < 2) else fib(n-1) + fib(n-2) inputLine = input() try: N = int(inputLine) except: N = len(inputLine) print([fib(n) for n in range(N)]) ''' # Example 2.1: Program still works as expected run(p2,'7') # --> [1, 1, 2, 3, 5, 8, 13] # Example 2.2: And now runs (at least halts) on itself as input run(p2, p2) # --> [] (why?) ############################################################################## # Step 3: run a program that does something interesting with itself as input ############################################################################## # Now let's write a program that does something vaguely interesting # with itself as input... p3 = ''' import sys def getAllInput(): # reads until EOF return sys.stdin.read() def findTopLevelFns(code): fns = [ ] for line in code.splitlines(): lineItems = line.split() if ((len(lineItems) >= 2) and (lineItems[0] == 'def')): fns.append(cleanFnName(lineItems[1])) return fns def cleanFnName(fnName): # fnName is either just the name, or perhaps the name followed # by the parameters. So we exclude chars from the left-paren onward. i = fnName.find('(') return fnName if (i < 0) else fnName[:i] def main(): code = getAllInput() print(findTopLevelFns(code)) main() ''' code = ''' def f(x): return x+1 def g(x): return x+2 ''' # Example 3.1: run on a simple case: run(p3, code) # --> ['f', 'g'] # Example 3.2: And now it does something interesting with itself as input: run(p3, p3) # --> ['getAllInput', 'findTopLevelFns', 'cleanFnName', 'main'] ############################################################################## # Step 4: The Halting Problem ############################################################################## # Definition: halts(program, input) returns True if the given program # ever halts (stops running, even if by crashing) on the given input, # and False otherwise (that is, if the given program runs forever on the # given input). # One way to try to write halts(program, input) is to simply run the given # program with the run() function above. But... This does not work. # We can run it until it halts (with or without a crash). # But how do we know if it NEVER halts? How can we return False here? def halts(programString, inputString): try: run(programString, inputString) except: pass return True # So: let's just ASSUME that someone somehow was super-clever and figured # out a way to write this halts() function. So? Well, then we can write # this program, that uses that halts() function: p4 = ''' import sys programString = sys.stdin.read() # assume the input is a program inputString = programString # provide the program as input to itelf! if (halts(programString, inputString)): print('Running forever!') while True: pass else: print('Halting!') ''' # Example 4.1 run haltingProblem (p4) on code that hangs: code = '''while True: pass''' run(p4, code) # --> Halting! (if halts() works correctly) # Example 4.2: run haltingProblem (p4) on p3 from above: run(p4, p3) # --> Running forever! (because run(p3, p3) halts) # So....? Intuition suggests this is at least VERY HARD to do. # For example: prove Fermat's Last Theorem, Goldbach's Conjecture, ... # (Note: we did not discuss how you could use the Halting Problem # to prove FLT or Goldbach's, so you are not responsible for that. # But, of course, we did do the following: # And, in fact... # Example 4.3: THE HALTING PROBLEM run(p4, p4) # --> WHAT HAPPENS?!? # We see: # run(p4, p3) hangs (runs forever) because run(p3, p3) halts. # And so: # run(p4, p4) should hang if run(p4, p4) halts (and vice versa). # And that is impossible. # And that is the halting problem! # So: it is IMPOSSIBLE to write the function halts(program, input) # that always returns True or False for arbitrary programs and inputs. # So what? # Well, if you can't even tell if a program is going to halt on an input, # how can you tell anything else that is interesting, such as whether or # not the program WORKS (that is, it halts and produces the correct output)? # (You can't.) # Uh oh.

# You are not responsible for the following code, and can ignore everything # from here onwards, but this is an example program that ignores its # input, and only halts if Goldbach's Conjecture is False, and hangs # (runs forever) if Goldbach's Conjecture is True. def findGoldbachViolation(): # halt if/when we find an even number > 2 that is not the sum of two primes def isPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False for factor in range(3,round(n**0.5)+1,2): if (n % factor == 0): return False return True def goldbachWorks(even): # return true if this even is the sum of two primes, false otherwise for p in range(2, even): if (isPrime(p) and (isPrime(even-p))): return True return False even = 4 while True: if (even%(1000*10) == 0): print(even) if (not goldbachWorks(even)): print('Found the violation at even =', even) return False even += 2 # never halt if Goldach's conjecture is True findGoldbachViolation()