 | | From: | Thomas A. Li | | Subject: | Who introduced Nondeterministic Turing Machine? | | Date: | Sun, 23 Jan 2005 08:59:48 -0500 |
|
|
 | Who introduced nondeterministic Turing Machine? Where is the proof?
Thanks.
Thomas Li
|
|
| | From: | r.e.s. | | Subject: | Re: Who introduced Nondeterministic Turing Machine? | | Date: | Sun, 23 Jan 2005 18:16:58 GMT |
|
|
| "Thomas A. Li" wrote ...
> Who introduced nondeterministic Turing Machine?
> Where is the proof?
In his 1937 paper, Turing introduced them as
"choice machines ... whose motion is only
partially determined by the configuration".
What we call a deterministic TM, he called an
"automatic machine".
You can find his paper online -- Google for
"On Computable Numbers, With an Application
to the Entscheidungsproblem"
--r.e.s.
|
|
| | From: | Thomas A. Li | | Subject: | Re: Who introduced Nondeterministic Turing Machine? | | Date: | Sun, 23 Jan 2005 20:45:19 -0500 |
|
|
| Thank you very much for your help. I had tried to find the word
"nondeterministic" there at vain.
Thomas Li
"r.e.s." wrote in message
news:uSRId.3620$YD5.631@newsread3.news.pas.earthlink.net...
> "Thomas A. Li" wrote ...
> > Who introduced nondeterministic Turing Machine?
> > Where is the proof?
>
> In his 1937 paper, Turing introduced them as
>
> "choice machines ... whose motion is only
> partially determined by the configuration".
>
> What we call a deterministic TM, he called an
> "automatic machine".
>
> You can find his paper online -- Google for
> "On Computable Numbers, With an Application
> to the Entscheidungsproblem"
>
> --r.e.s.
|
|
| | From: | examachine at gmail.com | | Subject: | Re: Who introduced Nondeterministic Turing Machine? | | Date: | 23 Jan 2005 07:41:43 -0800 |
|
|
| You can find the definition of an NDTM and its equivalence to an
ordinary TM in any theory of comp. textbook I suppose.
Regards,
--
Eray
|
|
