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???"