Week 10: Computability and Confusion

            Computability is the first topic in CSC165 that is new to me.  It is both interesting and somewhat confusing.  Unfortunately, any confusion is undesirable at this point in the course.  After thinking about my confusion, I realize that the halting problem is the culprit.  Why is this?

Elementary Definitions and Theorems:

            First, the stuff that makes sense.  Consider a set of inputs $I$ and a set of outputs $O$.  Computability begins with three relatively simple definitions and a single theorem.

Definition 1:  Let $f: I \to O$ be a function.  Then $f$ is well-defined $\iff$ for each $x \in I$, there is a unique $y \in O$ such that $f(x) = y$.

For remaining definitions and theorems, let $g, h: I \to O$ be well-defined functions.

Definition 2:  Then $g$ is computable $\iff$ there is a program $P$ such that $\forall x \in I, g(x) = P(x)$.

Definition 3:  Then $g$ reduces to $h \iff g$ can be implemented with $h$.  Below is what $g, h$ look like in Python code if $g$ reduces to $h$.  Let $P$ be the implementation of $g$ and $Q$ be the implementation of $h$.

            def P():
            """An implementation of the function f."""

                        Q():

Theorem 1:  Let $g$ reduce to $h$.  Then $h$ is computable $\implies g$ is computable.

The Confusing Part:

            Now, the stuff that is not so clear.  The function halt(f, i) tells us if a function $f$ with an input $i$ halts.  The halting function is not computable.  The proof of this statement starts simple enough:  Assume to the contrary that there is an implementation of halt(f, i) that works for all functions and inputs.  Then consider the function what_is_love(f):

            def what_is_love(f):

                        if halt(f, f):

                                    while True:

                                                print(“Look to the skies.”)

                        else:

                                    print(“Nobody knows.”)

The “while True” statement is the incomprehensible part of the proof.  I ask in lecture why it is there.  The instructor lets a classmate several rows ahead of me answer my question.  The explanation takes nearly half a minute.  I did not get any of it.  Apparently, the instructor did not have any problems with the explanation nor did my other classmates.

The Comprehending Part:

            It takes several days for me to understand why the “while True” statement is there.  Eventually, I look at what we are proving.  We assume that there is an implementation of halt(f, i) that works for all functions and inputs.  To disprove, we only have to show that one function and input does not work for halt(f, i).  This is a classic existential proof.  We are free to construct the function what_is_love(f) however we want to so long as it disproves the computability of halt(f, i).

            The “while True” statement guarantees that what_is_love(what_is_love) goes into an infinite loop if halt(what_is_love, what_is_love) returns True.  Likewise, what_is_love(what_is_love) halts if halt(what_is_love, what_is_love) returns False.  This is the contradiction and it disproves the computability of halt(f, i).  I wonder why that classmate who answered my question did not explain it like this....