|
|
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.
|
|
