Path: utzoo!utgpu!attcan!uunet!husc6!mailrus!cornell!blandy
From: blandy@lakshmi.cs.cornell.edu (Jim Blandy)
Newsgroups: comp.misc
Subject: Re: What's a TM?
Message-ID: <19965@cornell.UUCP>
Date: 4 Aug 88 19:37:42 GMT
References: <19918@cornell.UUCP> <934@netxcom.UUCP>
Sender: nobody@cornell.UUCP
Reply-To: blandy@cs.cornell.edu (Jim Blandy)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 66

In article <934@netxcom.UUCP> ewiles@netxcom.UUCP (Edwin Wiles) writes:
>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.

Oh dear.  Should this really be discussed here?  I'd move this to
another newsgroup, but I'm not sure this debate is interesting enough;
it's kind of old-hat.  Follow-ups through mail, please?

Yes, you're right.  Because they have infinite memory, Turing machines
are more powerful than current computers.  Nonetheless, they are still
used to model the capabilities of computers.

In reality, since any computer has a fixed amount of storage
(including disk storage), it has only a finite (big, but finite)
number of different states.  Thus, it can actually be modeled by a DFA
(Deterministic Finite Automaton).  But that's not an interesting thing
to work with.

Why?  Because DFAs are incapable of doing things like parsing and
type-checking, simple arithmetic, etc. unless you put a fixed limit
on the length of the program or the precision of the arithmetic.  But
one isn't interested in proving things about limited architectures;
one wants to be able to prove that no architecture will ever be able
to solve a certain problem.

A DFA-based argument can prove statements like:

    "No computer with this particular memory size can solve this problem."

So what?  Add more memory.  With TM-based arguments, we can prove
things like:

    "No computer will ever be able to solve this problem, no matter
     what the memory size."
	
The latter kind is more interesting; thus, we use TMs.  When we reason
about what a computer can do, we want a general argument, not one that
assumes a certain memory size.

>Also, solving certain problems requires the TM to 'fork' (make copies
>of itself, which take the alternate path, or paths).

Okay.  You're talking about non-deterministic algorithms, where one
gives the TM a choice of courses to take; the theory is that the TM
will always 'guess' the correct path to take.  But it's guaranteed
that any non-deterministic TM can be simulated by a normal TM.  The
normal TM may solve the problem much more slowly, but the power is the
same.

Note that any problem requiring infinite space also requires infinite
time.  Can a TM requiring infinite space (i.e., taking advantage of
its unlimited memory) be truly said to 'solve' the problem?  It'll
never stop and give you the answer...  A computer can do anything a TM
can do, if one insists that the TM must halt and that the computer has
sufficient memory.

My simulation will not handle non-deterministic Turing machines. :-)
--
Jim Blandy - blandy@crnlcs.bitnet
"And now," cried Max, "let the wild rumpus start!"