Can Computation Theory Be Taught in an Interesting Way?
                              Ching-Kuang Shene
                       Department of Computer Science
                      Michigan Technological University
                             1400 Townsend Drive
                             Houghton, MI 49931
                                shene@mtu.edu

MOTIVATION

In the mind of many students, a theory course is boring, dry, useless, and
lacks interesting topics except for, possibly, the "Halting Problem." The 
field of computation theory was born in 1936 when Turing proved that the 
Halting problem is undecidable.  It is hard to believe a field that has been 
developed for nearly 70 years has no interesting topics to teach.  Perhaps, 
it is because we do not look back and search for interesting ways to teach 
our students.  To address this problem, we take the recursive function 
theory approach using the concept of programming.   However, we need to 
sacrifice a little rigor in some non-essential places: modern computers are 
equivalent to Turing machines, and any program can be compiled to an integer. 
These two gaps can easily be closed later on.  The proposed computation 
theory component contains a number of basic elements: (1) self-reference, 
(2) simple reduction, (3) universal programs, (4) diagonalization, 
(5) the s-m-n (parameter) theorem, and (7) Rice' theorem.  This poster will 
illustrate how we can reach very far easily in a short period of time.

SELF-REFERENCE

Self-reference means a program acts on its on and is the source of many
fundamental result in computation theory, the Halting problem included.
If the Halting problem were computable, there would be a Boolean function
HALT(P,x) that takes a program P and its input x, and returns TRUE if P halts
on x for all possible pairs (P,x).  Consider a new function H(x):

     FUNCTION  H(x)
     {
          while (HALT(x,x));
     }

Therefore, "H(x) halts iff not HALT(x,x)."  Since "H() halts on input x" 
means "HALT(H,x) is TRUE," we have "HALT(H,x) iff not HALT(x,x)."  Replacing 
x with H yields "HALT(H,H) iff not HALT(H,H)."  This is a contradiction and 
HALT() is not computable.  The same self-reference technique can be used to 
show that there is no universal anti-virus program.  

SIMPLE REDUCTION

This technique helps reduce a problem to another that is known to be not
computable.  Suppose we want to show testing if a function is a constant 
is not computable.  Since we know HALT() is not computable, if we can write 
a function such that its constantness depends on HALT(), we are done.  Take 
an arbitrary program P and construct the following function:

     FUNCTION  Const(x)
     {
          while (!HALT(P,P));
          return c;  /* c is a given constant */
     }

It is not difficult to see that "Const(x) is a constant function iff 
HALT(P,P)." Since HALT() is not computable, determining if Const(x) is a 
constant is not computable either.  Hence, we reduce constant testing to 
HALT.  Similarly, testing if two programs P and Q have the same input/output 
behavior is not computable, because this test is equivalent to testing if 
P-Q is the zero function.  Thus, determining if an old system and a 
redesigned  one are the same I/O-wise is not computable.

A UNIVERSAL PROGRAM

A universal program is simply an interpreter that accepts a source program,
translates to a machine language (e.g., JVM), and interprets the instructions.

DIAGONALIZATION

By carefully choosing an assembly language and object code format, a source
program can be translated to a set of assembly instructions, which are
assembled into a non-negative integer.  Conversely, given a non-negative
integer, we can DISASSEMBLE it back into a set of assembly instructions, 
which can be converted to a source program.  Thus, we can view non-negative 
integers as programs!  Consider the following table in which the top row 
shows the input augments, the left column contains the program "numbers," 
and the entry on row i and column j is T if the disassembled program i runs 
on input j halts.

        0  1  2  3  4 ....
     0  X  .  .  .  .
     1  .  X  .  .  .
     2  .  .  X  .  .
     3  .  .  .  X  .
     4  .  .  .  .  X
     :

Let G(x) = NOT "the output of program x runs on input x".  More precisely, 
G() returns the opposite value of running program x on input x.  Is function 
G() one of the above list?  No, because G(), in fact its program "number," 
is different from any one on the list.  Therefore, G() cannot be computable;
otherwise, G() has a program that can be compiled to one of the program 
numbers, which is a contradiction.

THE S-M-N THEOREM AND RICE'S THEOREM

The s-m-n theorem states that a function can be rewritten in the calling
environment so that some of its original arguments can be taken out from the
argument list and absorbed into the function (i.e., runtime source-to-source
translation).  The s-m-n Theorem leads to Rice's Theorem, which states that 
no algorithm exists to determine from the description of a program whether 
or not the input of that program is a non-empty proper set of non-negative 
integers. Therefore, testing if a program will take a particular input and 
generate a given output is not computable.  Similarly, testing if a function 
is 1-1 or onto is not computable.

CONCLUSION

This effort grew out from a graduate theory course, and some materials
(i.e., self-reference, simple reduction and diagonalization) have been
used to help undergraduate students with weak theory background.  The proof
of the Halting problem was used in a CS0 orientation type course and was
well-received.  We anticipate that this approach will be further developed
into a web-based theory tutorial very soon.