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 ?
SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT