Path: utzoo!attcan!uunet!husc6!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.misc
Subject: Re: What's a TM?
Message-ID: <1164@garth.UUCP>
Date: 5 Aug 88 21:10:15 GMT
References: <19918@cornell.UUCP> <934@netxcom.UUCP> <19965@cornell.UUCP>
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 19

>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

Before you drop it, get the facts straight. Turing machines have unbounded
not infinite memory. The only way a Turing machine can write an infinite
tape is in infinite time, in which case it is busted.

>                                               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.

I'm not so sure, but I don't feel like looking it up. I suspect a
nondeterministic machine can navigate through a partial function by
making good guesses while a backtracking deterministic machine might
blunder into a computational blackhole. Or maybe not.