Content deleted Content added
→top: Added {{Skip to talk}} template |
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 |
||
Line 487:
: Now, back to the subject after I've thought about it again. By [[Generalization|definition]], concept {{mvar|A}} is a ''[[special case]]'' or ''specialization'' of concept {{mvar|B}} precisely if and only if every instance of concept {{mvar|A}} is also an instance of concept {{mvar|B}}, but there are instances of concept {{mvar|B}} which are not instances of concept {{mvar|A}}. Non-deterministic Turing machines (NTMs) [http://books.google.com/books?id=oG6lRcwRqCUC&pg=PA14&lpg=PA14&dq=ntm+working+as+dtm&source=bl&ots=yknFtR37TK&sig=ssLZaOiAUIftTgphRdTxXf7LHok&hl=en&sa=X&ei=fultU_D4A4eg7Abp_4DYBw&redir_esc=y#v=onepage&q=ntm%20working%20as%20dtm&f=false can be restricted] so they work as deterministic Turing machines (DTMs), while an ''ordinary'' DTM (not its multi-tape variations or anything else) can't work as an NTM. Thus, by the definition, NTMs are a special case of DTMs{{snd}} and that's the way {{Diff|Computational complexity theory|607300863|607300453|I've edited}} the article.
: 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)
| |||