|
Re: On NP Completeness and Intractability
Posted:
Nov 1, 2005 5:38 AM
|
|
Willem wrote: > Robert wrote: > ) For each real number x, consider the decision problem D(x) defined as follows: > ) > ) Given rational number r, decide whether r < x. > > Some would say that that is not a valid definition of a decision problem, > because you are only speculating about its existence, and not actually > describing any single decision problem. This probably boils down to the > axiom of choice in some way. > > I think such a decision problem D(x) is decidable iff it can be described. > > In any case, the more interesting question is how many *describable* > decision problems are decidable ? You can't hope to solve a problem > if you can't even specify it, after all. > > ) Note that if an algorithm to solve D(x) exists, x must be constructive in a > ) rather strong sense: in particular, the sequence of decimal digits of x is > ) recursive. There are of course only countably many such x. > > I'm not sure what you mean by 'the sequence is recursive'. Does this > include PI, for example ?
In Turing landmark paper, he was interested in the "computable numbers", those real numbers that can be approximated to an arbitrary accuracy by a Turing machine.
http://en.wikipedia.org/wiki/Computable_number
This includes all rational and algebraic numbers, and some trancendental numbers, including PI. But, there are uncountably many real numbers, so most real numbers are not computable.
|
|