From: mcgrath@cs.uiuc.edu (Robert McGrath)
Subject: Re: Theoretical Computer Science
Reply-To: mcgrath@cs.uiuc.edu
Organization: University of Illinois, Dept of Computer Science
Date: Fri, 11 Dec 1992 18:46:33 GMT

In article <1g85nrINNoo8@iraul1.ira.uka.de>, s_titz@ira.uka.de (Olaf Titz) writes in part:
|> 
|> >concede that ANY problem that can be solved can be solved in
|> >one step.  Not only does P == NP, but all computation is trivial!
|> 
|> but this is not right any more. It is not claimed (not by me, at
|> least) that precognition can even just improve the solution for ANY
|> problem. It *may* be able to determine a solution for SOME problems,
|> but not more. (Remember that the Halting Problem is not about
|> determining infinite loops in some programs, but in ANY program. That
|> is a big difference.)
And if even a few problems can be solved this way, the theory is
"a little bit pregnant".

|> [Code-breaking is calculated on]
|> >the actual amount of inherent "impracticality" and force it to be
|> >big enough to be "impossible" under certain assumptions and for certain
|> >purposes.  Such extimates have always assumed the non-existence
|> >of telepathy, precognition, and PK.
|> 
|> Right, but the mere existence of such phenomena does not imply that
|> they would make code-breaking easier.
All that matters is that they MIGHT make code-breaking easier.  If
that is true, then the entire purpose of the code is undermined.


|> >computer science is the source of claims that the human brain is,
|> >in principle, equivalent to a TM.  If this is NOT true, it is a
|> >very important finding for both psychology and CS, because we have
|> >to deal with two apparently similar systems with radically
|> >different capabilities.
|> 
|> You got it! Some CSists have claimed, from their understanding of
|> formal systems, that the brain works just that way. Based on this
|> premise is the strong AI theory - research into the field how machines
|> can emulate human intelligence. If you negate the premise, *this* gets
|> broken, but not the large fields of CS that deal entirely with
|> *machines* in their own right - from computability theory (the theory
|> on what can be computed *with machines*) to software engineering.

If you recall my comments, you will remember that I restricted myself
to two basic topics:  theory of comutability and encryption/suthentication.

I never claimed that all activities that occur in the vicinity of
computers would be affected by my comments.


|> No doubt that this would be interesting and leading to new textbooks.
|> :-) But to design a machine to have ESP abilities, you first had to
|> have a working theory on how ESP works (yet to come), then this theory
|> had to imply that ESP can be done with certain machines (doubtful), it
|> had to imply that ESP is based on a formal system, (which is the only
|> thing that can be done which machines that are defined as formal
|> systems themselves) which is even more unlikely given the fact that
|> there exist concise theories on certain phenomena that CANNOT be
|> described by formal systems (take the position of an electron in an
|> atom. This is impossible to determine, as quantum mechanics shows).

Recall that the entire discussion was based on the PREMISE that 
ESP exists (which I doubt).  Since noone can describe it,
it is impossible to say what it ISN'T.

You seem to think that computers are not physical entities!
I would point out that, if ESP exists and is mediated by some
not-yet-known mechanism, there is no reason why the mechanism
cannot, in principle, be used by machine (since we don't know
anything about it).  You seem to dismiss the possibility of
circuits or devices which might interface between conventional
materials and "ESP-mitters" or whatever.  Remember, real,
physical, computers operate by using the very same quantum 
phenomena you indicate are indescribable by formal systems!

(The software engineers mottoe:  there will be new hardware 
next year, and then all our problems will be over! :-))


|> >I should also note that it can be claimed that NOTHING is outside 
|> >the domain of ESP.  ESP can do ANYTHING.  ESP can go faster than 
|> >the speed of light, backwards, and forwards in time: effectively 
|> 
|> This is an unfortunately common misconception of ESP. Just from
|> stating that ESP can do something that is not explained by current
|> physics theories you conclude that ESP can do *everything* that is
|> denied by physics. This is a bit farfetched. Once there is a theory on
|> ESP, it will probably include a set of borders which ESP can *not*
|> cross. 

When there is a theory of ESP, I will use it.  Until then I use
the union of all claims made about it.  (Bear in mind that this
is for purposes of argument.)

-- 
  Robert E. McGrath
  Urbana Illinois
  mcgrath@cs.uiuc.edu