Path: utzoo!utgpu!attcan!uunet!husc6!cmcl2!nrl-cmf!ukma!david
From: david@ms.uky.edu (David Herron -- One of the vertebrae)
Newsgroups: comp.sys.amiga
Subject: Re: What's a TM?
Message-ID: <10130@e.ms.uky.edu>
Date: 4 Aug 88 00:27:03 GMT
References: <19918@cornell.UUCP>
Reply-To: david@ms.uky.edu (David Herron -- One of the vertebrae)
Organization: U of Kentucky, Mathematical Sciences
Lines: 28

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.


The equivalence doesn't work in both directions.  TM's have an infinite amount
of memory available to them whereas physical computers do not.  Therefore
there is a significant class of problems which can only be solved by TM's,
or rather by theoretical machines as opposed to physical machines.

Other than this little point everything you said is true enough.  If I
wanted to be that picky I'd point out that TM's halt when they halt, not
when they "see a character they don't know how to deal with".  That is,
they reach an accepting state ... but this is a minor technical point
unlike the point in the previous paragraph.

Ok, now you've proved that DME is no more powerful than vi.  You need
to send this TM simulator off to comp.sources.misc so that it will
be able to keep the TM simulator for vi company :-).


-- 
<---- David Herron -- The E-Mail guy                         <david@ms.uky.edu>
<---- ska: David le casse\*'      {rutgers,uunet}!ukma!david, david@UKMA.BITNET
<----
<---- Looking forward to a particularly blatant, talkative and period bikini ...