Content deleted Content added
Added a comment concerning Gödel's Incompleteness Theorem |
Note about "decision problems" and "function problems" |
||
Line 492:
::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)
== Difference between "decision problems" and "function problems" ==
We read
<blockquote>It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a, b, c) such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.</blockquote>
This does not sound correct at all. Consider the predicate "pfactors([f0...fn],composite)", which is TRUE if [f0...fn] are the prime factors of the composite. Evidently, the decision problem "pfactors([f0...fn],composite)" is MUCH easier than the function problem "pfactors([F0...Fn],composite)" where F0 ... Fn are variables to be determined and even n is unknown. Additionally, in the given example, there may be ways to check whether a x b = c holds much more easily than actually computing a x b (we just need to "fail fast" after all). Additionally, the text says "function problems can be recast as decision problems" and then proceeds to given an example where a decision problem is recast as a function problem...
See also for example FNP vs. NP : https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fnp (which I don't quite understand yet) [[User:There is a T101 in your kitchen|There is a T101 in your kitchen]] ([[User talk:There is a T101 in your kitchen|talk]]) 21:46, 8 October 2016 (UTC)
| |||