CIS115: What is Computable?

(MacCormick, Chapter 9)

FOLLOW ALONG: www.cis.ksu.edu/~schmidt/halting.html

Computers calculate on numbers (represented as 1s and 0s), on text, sounds, images, voltages, etc. (all represented as numbers). Are there some calculation activities that are beyond the reach of computers, that they cannot do? The answer is yes.

The Starting Law of the Universe

You have to start somewhere. We start with this law:

Something is different from nothing.

That is, Something ≠ Nothing. Mathematicians use 1 for Something and 0 for Nothing. So,

1 ≠ 0

All mathematics starts from here.

So does Western Thought. A sentence can be an imperative (e.g., "Do your homework!"), a question ("Are we there yet?"), or a declaration ("The sky is blue.")

Here, we care about declarations.

The declaration, "The earth is round" is a fact; it says something; it is True; it is 1.

The declaration, "The moon is made of green cheese" is a falsehood; it says nothing; it is False; it is 0.

Logicians say that

True ≠ False

No declaration can be a fact and a falsehood at the same time. A declaration like, "It is daytime." is a fact at some moments in the universe and a falsehood at others, but it is never both at the same moment.

If we abuse English and write a declaration that is both a fact and a falsehood at the same moment, it is a paradox and must be discarded from the English language --- it is nonsensical; it cannot be. A paradox makes True = False, which violates the starting law of the universe.

The oldest known example of a paradox is the sentence, "I am lying." --- the declaration is a fact exactly when it is a falsehood (since "lying" means "stating a falsehood"). This is the Liar's Paradox. The Liar's Paradox is nonsensical; it cannot be.

Here is a little story called the Barber's Paradox, due to Bertrand Russell. It will be the centerpiece of the next section:

There is a lone village on an island where the village barber cuts the hair of exactly all those people who do not cut their own hair. Now, is this declaration a fact or a falsehood? The barber cuts her own hair.

Russell's Paradox

Bertrand Russell was a 20th-century philosopher, mathematician, logician, and a Nobel-prize winner in literature. He found a famous paradox in mathematics, one that spread into computing.

Declarations in mathematics are called predicates; here are examples:

3 > 2 (a fact)

x = (x + 1) (a falsehood, regardless of x's value)

(x + y) = 5 (a contingency --- sometimes a fact, sometimes a falsehood, depending on the values of x and y)

Mathematics is the science of discovering predicates that are facts.

Mathematicians has always worked with numbers, but in the nineteenth century, mathematicians started using predicates to define sets. (Recall that a "set" is a collection --- a "grocery sack" --- of elements. Examples: {4,5,6} is a set of three numbers. {} is a set of no numbers.)

Here are examples of sets of numbers, defined with predicates. (Read the first one as, ''the set of elements, n, such that n > 0 is a fact.'')

{ n | n > 0 } (the positive numbers)

{ m | m + m = 0 } (there is only one element, 0)

{ m | not(m + m = 0) } (all numbers except 0)

{ x | x > 0 and x < 3 } (the numbers between 0 and 3)

The whole point of defining a set is to ask what's in it. The predicate, e ∈ S, is a fact exactly when element e is contained in set S. (Read as "e is in S".) Here are examples:

5 ∈ {4,5,6} is a fact.
3 ∈ {n | n > 0} is a fact because, when we replace n in n > 0 by 3, we find that 3 > 0 is a fact.
3 ∈ {m | not(m + m = 0)} is a fact because not(3 + 3 = 0) is a fact.
3 ∈ {m | m + m = 0} is a falsehood because 3 + 3 = 0 is a falsehood.

Mathematicians use sets to hold sets, too. Here are examples:

{ S | 4 ∈ S } (the sets containing 4)

{ S | True } (the set of all sets --- call this the universal set, U.)

{ S | S ∈ S } (those sets that contain themselves (!))

Some examples of membership predicates for the above sets:

{4,5,6} ∈ {} is a falsehood

{4,5,6} ∈ {S | 4 ∈ S} is a fact

{4,5,6} ∈ {S | S ∈ S} is a falsehood

{} ∈ U is a fact

U ∈ U is a fact (!)

U ∈ {S | S ∈ S} is a fact

The last two facts intrigued Bertrand Russell, and he defined this set, the Russell set:

Let R be the name of the set, {S | not(S ∈ S)}

R is the collection of the sets that do not contain themselves. Clearly, {4,5,6} ∈ R is a fact, and U ∈ R is a falsehood. But what about R ∈ R?


RUSSELL'S PARADOX:

    Let  R  be  {S | not(S ∈ S)}
                        ↑
R ∈ R                   ↑ 
is a fact exactly when not(R ∈ R)
                       is a fact, that is, exactly when  
                                           R ∈ R is a falsehood

R ∈ R  is a paradox!

Russell's Paradox is generated by the combination of S ∈ S (self-inspection) and not ("flipping" the answer) --- a real disaster!

We have uncovered something that mathematics cannot do --- define a set of sets that don't hold themselves. Modern versions of set theory disallow self-inspection to remove this form of paradox.

Computer programs can do self-inspection

Russell's paradox follows us into computer science and causes Turing's halting problem, and we'll see why. First, we note that self-inspection is an important activity in computing. On Page 182, MacCormick shows a picture of MS Word inspecting itself:

That is, a human loaded and started WIN-WORD.EXE on the computer's processor, and the human told the running program to load as the input, WIN-WORD.EXE.

Editor programs, like MS Word, can inspect all programs, including themselves. Compiler/interpreter/IDE programs can inspect/compile/run most all programs, including themselves. Error-finding, performance-analyzing, and correctness-checking programs are can inspect/analyze a wide range of programs, including themselves.

A key feature of computer programs, one that leads us into artificial-intelligence-like areas, is that they can inspect other programs, including themselves.

How far can these inspections go? We will see that they can generate paradoxes!

Alan Turing and the Universal Turing Machine

Alan Turing was an English mathematician, employed by the British government to break the codes the Nazi armies used for communication. Turing and his team succeeded, and the Allies used the decoded Nazi communications to win World War II.

Turing was interested in machines for calculating mathematics. His imaginary Turing machine was a controller with a read-write head that traversed the squares of an unbounded roll of toilet paper, where only a 0 or a 1 can be written in a square:

Turing realized that the controller could be wired as a "processor" that understood these six instructions:


* move Left/Right one square
* erase the square (make it blank)
* write 0/1 on the square
* if square is blank/0/1, then goto Instruction #n
* goto Instruction #n
* stop

Here is a sample program that scans a binary number from left to right and flips all 0s to 1s and all 1s to 0s:


#1: if square is 0, then goto #4
#2: if square is 1, then goto #6
#3: if square is blank, then goto #9
#4: write 1
#5: goto #7
#6: write 0
#7: move Right
#8: goto #1
#9: stop

 ... => ...

The nine instructions have number codings, and the program can be copied onto a tape as one huge (Base-2) number to be read by the controller. The Universal Turing Machine was configured like this:

The Universal Turing Machine is the origin of

CPU
linear storage
stored program
binary machine language

Turing wrote programs for the Universal Turing machine, and he believed that all facts/knowledge/problems that can be calculated/deduced/solved by a machine can be done by a Universal Turing Machine. This is now known as the Church-Turing thesis.

(The "Church" part refers to Alonzo Church, a Princeton mathematician who developed a symbol system, the lambda-calculus, which has the same computational powers as Turing's machines.)

Turing asked: Are there some problems whose solutions cannot be calculated by his machine? In particular, he wondered,

Is there a program that can read the coding of any program and correctly predict whether the latter will halt when it runs?

This question is called the Halting Problem. Its answer is no. (If the answer were yes, then the program would let us build Russell's paradox in the computer!)

Requirements, implementations, convergence and divergence

These definitions are crucial:

A requirement is a statement of a job to do (e.g., ``compute square root!''). An algorithm is a sequence of instructions that implements (solves) the requirement. A program is the algorithm written in binary computer language (1s and 0s) --- a computer program is a long, huge nonnegative number.
A computer processor runs a program by doing its instructions. A program requires an input (a number or a pair of numbers) to start its work. To keep it simple, the numbers are always nonnegative integers (0,1,2,...).
The computer processor does the calculations stated in the program. If all goes well, the program converges (halts, terminates) and emits an output, a number. If something goes wrong and no output is emitted, the program diverges (loops, freezes, goes lost, runs forever, hangs).

The above story is simplified, but text editors, web browsers, operating systems, etc., follow these principles.

Here are two examples of requirements:

A requirement for a program that squares an input number, n:
n => ↓(n²)
Read it as ''from input n, the program must converge with output n².'' This algorithm implements the requirement:
```
INPUT: a number,  n
OUTPUT: a number
ALGORITHM: 1. read  n  
           2. calculate  answer = n * n
           3. write  answer
```
Say that the program we write from the algorithm is named square. Then,
run(square)(3)↓9
says that the computer ran the program with input 3 and converged with output 9.
A requirement for a program that computes square root for some, not all, numbers (remember, our numbers are 0,1,2,3,...):
```
n =>  ↓m  iff  m² = n
  =>  ↑   iff  there is no  m  such that  m² = n
```
Read iff as "exactly when" and ↑ as ``diverges.''
This requirement might be implemented by a program that reads n and guesses possible answers (0,1,2, etc.) until an output, m is found, if ever. (If not, the program runs forever.)
Say that sqrt is the name of the program we build. Here are two uses of it:
run(sqrt)(25)↓5
run(sqrt)(7)↑

The examples show that convergence to an answer is some-answer, something; divergence is no-answer, nothing. That is, for every computer program, p, and datum, d,

run(p)(d)↓answer ≠ run(p)(d)↑,

which is the ``first law'' of the computing universe.

Turing's Halting Problem

Remember that a program is an algorithm written in a computer language of 1s and 0s --- a computer program is one long, huge nonnegative number. This means a computer program (number) can be input to another computer program, which can choose to run the input. Here is a requirement that demands this:


 p =>  ↓(a + 1) iff  run(p)(0)↓a
   =>  ↑        iff  run(p)(0)↑

The requirement demands we run input number/program p with datum 0 and add one to its answer, if there is one. There is an easy algorithm:

INPUT: a program, p, coded as an integer
OUTPUT: a number or ↑
ALGORITHM: 
1. do run(p)(0) and wait....
2. if run(p)(0)↓a, then produce output a+1
   (if run(p)(0)↑, then we are still waiting, and there is nothing we can do)

Not all such requirements can be implemented. In particular, Turing restated Russell's paradox as this requirement:


  p =>  ↓1 iff  run(p)(p)↑
    =>  ↑  iff  run(p)(p)↓answer 

If some program, named Russell, implemented this requirement, then

run(Russell)(Russell)↓answer  iff  run(Russell)(Russell)↑

which cannot be --- Russell would be a "paradox program"!

The requirement uses self-inspection (run(p)(p)) and then "flips" the answer --- in particular, ↑ is flipped to ↓1, which goes against intuition. (How can a computer program detect that another computer program "has gone lost"?)

It is not surprising that the above requirement can never become a program, but its consequences are many: There is an incredibly useful program that Turing proved is impossible to implement:

TURING'S HALTING PROBLEM:

Can we implement a program that analyzes another
program and its input and predicts in advance
whether the program-and-input will halt (converge to an answer)?

  p,d =>  ↓1 iff  run(p)(d)↓answer
      =>  ↓0 iff  run(p)(d)↑

The answer is no: If some program, named Turing, implemented the above requirement, then we could build the Russell program, like this:

INPUT: a program, p, coded as an integer
OUTPUT: ↓1 or ↑
ALGORITHM: 
1. run(Turing)(p,p) and obtain the output answer, which must be 0 or 1
2. if answer = ↓1 then diverge: ↑
   if answer = ↓0 then produce output ↓1

This generates an implementation of Russell's paradox, which cannot be.

From the Halting Problem, researchers showed that many other important requirements are also impossible to implement:

whether a program is free of all run-time errors
whether two programs produce exactly the same outputs from the same inputs
whether a program implements a requirement correctly

Almost all important features of computer programs can never be checked by other computer programs!

In practice, there are still text-editor, analyzer, and error-finding programs that can examine other programs, even themselves. But they cannot answer all the interesting questions about programs that we might like them to answer --- the best one can do is build a program that converges to a useful answer some of the time (like the sqrt program seen earlier does) and diverges lots of other times (because the program cannot discover an answer and "goes lost".)

Computing is constructive mathematics, and since mathematics has its limitations, so does computing.

Conclusion

The results stated here are the reason why people (and not machines) still design programs, write programs, analyze programs, test programs, and prove programs correct. They are the reason why you can get a job once you finish your training here and can have some hope of job security twenty years from now --- there are some activities computers will never be able to do.

Postscript: Computational complexity theory

Computers can implement lots of requirements, and there are lots of requirements that computers cannot implement. What if a requirement has an algorithm that is so slow that it takes a hundred years to compute an answer? How useful is that?

For better or worse, there are many critical requirements that have poor algorithms, and there is no known way to improve them. Such requirements are ``practically impossible'' or intractible. Here are examples of intractible problems:

You have a maze, and you want to calculate the shortest path of all the paths from the maze's entry to its exit.
You have a deck of cards, and you want to print all the shuffles of the deck.
You have a roadmap of cities, and you want to calculate the shortest tour that lets you visit each city.
You have a collection of differently sized boxes, and you want to load a van with the largest quantity possible of them.
You want to compute the inverse of a public key, calculated by RSA encryption, to eavesdrop on an internet transmission.

For realistically sized mazes/card decks/roadmaps/vans/keys, the best-known solutions to these requirements will take years --- even centuries --- to solve with Turing-machine-like computers. Furthermore, if you can find a significantly better solution to any one of these problems, the solution can be applied to all the others. But no one knows how to do it!

Computational complexity theory is the study of ``how fast'' algorithms are. Many requirements have fast (log-time and linear-time) algorithms, others have slow-but-tolerable (polynomial-time) algorithms, and others have intractible (exponential-time and worse) algorithms. Learning the details of computational complexity will help you become a computer scientist.