To highlight possible limits to predictability I've offered the

following paradox to both my students and colleagues. Many have felt

it to be a trivial paradox. However, they fail to agree on why it is

trivial offering several different resolutions. I will restrict my

commentsfor I have no resolution with which I am completely satisfied

and would be interested in fresh responses.

The year is, perhaps, early in in the next century. A computer and a

programmable robot are purchased from Radio Shack. Given the state of

the robot and computer at say 12:00PM, the computer is to predict the

position of the robot's arm at 2:00PM, stating its prediction at

1:00PM. The robot is programed to be contrary and raise its at 2:00PM

if and only if the computer has predicted that it won't. Which should

be returned to Radio Shack for a refund for its failure to perform as

advertised, the computer or the robot?

------------------- ---------------- --------------

Some feel the computer will just go into a loop. However, just as

Goedel avoided the loop of the liar paradox by substituting

provability for truth, so the computer is concerned only with the

computability of a set of equations which are guaranteed a solution

for reasonable initial conditions. The computer can't see the paradox.

Some feel the computer would require an infinite time, i.e. fail to

halt. What is needed is a finite time less than one hour. Though one

is guaranteed a solution to the equations, one is not guanteed a

"closed" solution. This distinction is crucial since a closed solution

can be calculated in a time that grows only logarithmically with the

time argument. Approximation procedures may grow exponentially with

the time argument.

As did Goedel's paradox, this paradox seems to expose an

incompleteness - an incompleteness in the set of "closed" functions.

Goedel's incompleteness theorem has led to unsolvability proofs for

various problems which could be "isomorphically" mapped to his

original variation of the liar paradox. What light might this

incompleteness in the set of "closed" functions shed on the existence

ofefficient algorithms for certain classes of problems. Perhaps, this

may address questions raised in Gordon D. Posch's 1996/05/01 thread:

"Halting problem<=>NP-completeness<=>Goedel's Theorem???"