For our final problem of the semester, we looked how we can put together the fundamentals of discrete mathematics we learned in this course to prove a remarkable fact: there are some computer programs that we can’t write. In particular, we showed that a function halts(f, x) cannot not exist. halts takes a function f and an input x to that function and returns True if and only if f(x) halts, i.e., returns a value. Note that by “exists”, we also assume that halts itself does not go into an infinite loop—that would be a rather useless function, otherwise!

Ultimately, our proof of this fact was a proof by contradiction. We assumed that halts exists and derived a contradiction from that assumption. Here is a partial version of the proof:

Proof. Assume that halts exists. Define the following functions loop and bad:

# An simple infinite loop
def loop():
    return loop()

def bad(f):
    if halts(f, f):
        loop()
    else:
        return 0

loop and bad are well-formed programs because we assume halts exists.

Complete this proof by analyzing the cases of execution of halts(bad, bad), i.e., the halts function when bad is given for both the function and input to that function. Since we assumed halts exists and does not go into an infinite loop, then there are two cases to consider:

• halts(bad, bad) -->* True
• halts(bad, bad) -->* False

In each case, consider how bad should have operated in order for halts to produce the desired result and observe the contradiction that arises. By showing a contradiction arises in both cases, we can conclude that our original assumption that halts exists must not be true!