A Computational Paradox

A Computational Paradox

Post by Douglas Tiberi » Thu, 14 Aug 2003 13:46:23



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

 
 
 

1. Theory: the priority paradox

Probably the _least_ realistic thing about Will Wright's 'The Sims' is
the way its characters calculate their priorities, at any moment.

But this same algorithmic challenge also applies to natural language
generation-- if we have limited bandwidth for speaking, we need to be
sure the highest priority information gets transmitted first.

And this is also relevant to natural language understanding-- we can
trim possible misreadings most efficiently, if we have a decent guess
about the speaker's priorities at the moment.

And in some sense, my criticism of the Cyc project [1] is that its
ontology bogs itself down in abstract trivialities, right at its root:

Thing
  Intangible
  IndividualObject
    Event
    Stuff
      Process
        SomethingExisting
          TangibleObject

More realistic priorities are embodied in a simple text-adventure
ontology:

  Thing
    Item: vehicle, food, container, clothing...
    FixedItem: switch, dial, button, decoration...
    Room

Calculating realistic 'artificial psychology', based even on the latter
ontology, is devilishly hard, though.  In reality, human priorities are
*non-linear* in the strong sense of chaos theory: any tiny flap of a
metaphoric butterfly's wings can cause a typhoon in the character's
instantaneous perception of what's important.

Where I'm noticing this recently, though, is in my timelines project [2]
and especially in some more-prose-y spinoffs of the timelines. [3] [4]

My idea for the spinoffs was to give a breezy overview of many
characters' lives, in parallel, but this only works if I _really_
understand what was important for each character at each point.  Any
time I bluff, that bluff is immediately obvious as a dilution of the
intensity (or, equally, the breeziness) of my prose.

So a great deal of the _labor_ of writing is what Joyce called 'French
polish'-- you go back over it and over it, looking for 'rough spots'
where the intensity flags-- where the writing fails to reflect the
appropriate priorities.  And in this process, whatever passage has best
achieved intensity/polish becomes the standard that the rest must be
adjusted to match-- it's this intuition of contrast between
higher-quality and lower-quality that guides the re-writer's efforts.

And, unhappily for the timelines spinoffs, getting just those right few
words, to put a character in just the right instantaneous perspective,
always seems to mean going off and reading a whole damn book on the
topic!

[1] Cyc:  http://www.robotwisdom.com/ai/cyc.html
[2] ITP: http://www.robotwisdom.com/science/history.html
[3] c1900 gossip: http://www.robotwisdom.com/jaj/gossip.html
[3] 1881f gossip: http://www.robotwisdom.com/jaj/gossip81.html
--
 http://www.robotwisdom.com/  "Relentlessly intelligent
yet playful, polymathic in scope of interests, minimalist
but user-friendly design." --Milwaukee Journal-Sentinel

2. XFree86 for OS/2 install

3. Simpson's Paradox and Quantum Entanglement

4. Schematic for RR501

5. fuzzy logic paradoxes?

6. HTTP server (again)

7. Fuzzy logic solves liar paradox?

8. Peacefire: Yahoo Mail accounts & others compromised

9. Cretan Liar's Paradox...an alternative

10. a so-called paradox...

11. AI Math induction paradox

12. Kleene-Rosser paradox ?

13. Searle's chinese room paradox