Path: utzoo!utgpu!attcan!uunet!seismo!sundc!hadron!netxcom!ewiles
From: ewiles@netxcom.UUCP (Edwin Wiles)
Newsgroups: comp.sys.amiga
Subject: Re: What's a TM?
Summary: Whoaaaa There!
Message-ID: <934@netxcom.UUCP>
Date: 3 Aug 88 13:51:19 GMT
References: <19918@cornell.UUCP>
Reply-To: ewiles@netxcom.UUCP (Edwin Wiles)
Followup-To: comp.misc
Organization: NetExpress Communications, Inc., Vienna, VA
Lines: 40

In article <19918@cornell.UUCP> blandy@cs.cornell.edu (Jim Blandy) writes:
>
>So a TM is a VERY SIMPLE computer, simple enough to write proofs
>about, but powerful enough to do anything any computer can do.  It's
>been proven already that anything a TM can do, a computer can do, and
>vice versa.

HOLD IT!  I'm not that far out of college (3 yrs), but I remember quite
clearly that TM's are a *super-set* of current computing technology.
i.e.  If a computer can do it, a TM can do it.  But it is not necessarily
true that if a TM can do it, a computer can do it.  (Quite often it is
true, but not always.)

As 'proof' for this:  If a problem requires infinite memory, or infinite
processors, it *can* be solved by a TM, but not by any existant computer.
(I know I'm stating this poorly, but that's the gist of it.)  The idea
being that the 'tape' a TM uses stretches into infinity, and there is
no way for a computer to "stretch into infinity".   Also, solving
certain problems requires the TM to 'fork' (make a copies of itself, which
take the alternate path, or paths).  Since a TM is purely imaginary, it
can do this indefinitely.  Standard hardware, even the heavy-duty parallel
processors, have a *finite* number of processors.

And before you start talking about virtual memory, and other such tricks,
let me remind you that you will still run into limits.  Like how much
addressing space do you have?  And, How much disk space do you have to
store the virtual machines that don't happen to be running right now?
And where do you store the results of all this computation?  On paper
created from all the trees now in existence? :-)

If anyone is heavily interested, I'll dig out my textbook and produce a more
detailed/correct answer.  Or, at the very least, tell you the title of the
text so that you can study it yourself.

					Enjoy!
-- 
...!hadron\   "Who?... Me?... WHAT opinions?!?" | Edwin Wiles
  ...!sundc\   Schedule: (n.) An ever changing	| NetExpress Comm., Inc.
   ...!pyrdc\			  nightmare.	| 1953 Gallows Rd. Suite 300
    ...!uunet!netxcom!ewiles			| Vienna, VA 22180