Path: utzoo!attcan!uunet!husc6!mailrus!ames!ucsd!nosc!humu!uhccux!lee
From: lee@uhccux.uhcc.hawaii.edu (Greg Lee)
Newsgroups: comp.misc
Subject: Re: What's a TM?
Message-ID: <2202@uhccux.uhcc.hawaii.edu>
Date: 6 Aug 88 15:25:20 GMT
References: <1164@garth.UUCP>
Organization: University of Hawaii
Lines: 13

From article <1164@garth.UUCP>, by smryan@garth.UUCP (Steven Ryan):
" 
" >                                               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

Any non-deterministic finite automaton can be simulated by a
deterministic one...  Could we have a reference for the case of TMs?

		Greg, lee@uhccux.uhcc.hawaii.edu