Content deleted Content added
Deltahedron (talk | contribs) →Reversal: The statement that any given NTM may be "restricted" to a DTM is not the same as saying that the concept of NTM is a restriction of the concept of DTM |
→Reversal: Replied |
||
Line 488:
: Thoughts? If I'm wrong, please point out where's that the case, so the monkey can learn to read better. :) — [[User:Dsimic|Dsimic]] ([[User talk:Dsimic#nobold|talk]] | [[Special:Contributions/Dsimic|contribs]]) 09:10, 10 May 2014 (UTC)
::You are misquoting the book you cite. It says that a NTM M can be restricted to a DTM M1 (by choosing one specific successor state) but it does not say that M1 computes the same function as M (which is how I understand your "works as"). Using the same search terms as you did, [http://books.google.co.uk/books?id=YnLmsHAtvYEC&pg=PA72&dq=%22ntm+working+as+dtm%22&hl=en&sa=X&ei=8u1tU8vlJoPlOsiRgfAD&redir_esc=y#v=onepage&q=%22ntm%20working%20as%20dtm%22&f=false here] we find "every DTM, by definition, is a special NTM" and [http://books.google.co.uk/books?id=n2jCfkPDcIsC&pg=PA31&dq=%22ntm+working+as+dtm%22&hl=en&sa=X&ei=8u1tU8vlJoPlOsiRgfAD&redir_esc=y#v=onepage&q&f=false here] "an NTM can be simulated by a DTM, i.e. every NTM has an equivalent DTM". I would say that an NTM is a TM in which at each point there is a number of successor states, and a DTM is a TM in which at each point there is one or none. So every DTM is an NTM, but some NTMs are not DTMs, namely those NTMs in which some states have more than one successor. The concept of DTM is a restriction of the concept of NTM, and the class of DTMs is a subset of the class of NTMs. The statement that any given NTM may be "restricted" to a DTM is not the same as saying that the concept of NTM is a restriction of the concept of DTM. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 09:23, 10 May 2014 (UTC)
::: Well, I admit, I was wrong. Thank you for the explanation, and I'll use it as a motivation to learn to read better. — [[User:Dsimic|Dsimic]] ([[User talk:Dsimic#nobold|talk]] | [[Special:Contributions/Dsimic|contribs]]) 09:50, 10 May 2014 (UTC)
| |||