In article <wPx9f.69135$S4.50236@edtnps84>, Oliver Wong <firstname.lastname@example.org> wrote:
>"Googmeister" <email@example.com> wrote in message >news:firstname.lastname@example.org...
>> No, actually most decision problems are undecidable. There are >> countably >> many Turing machines (like the integers), but uncountably many decision >> problems (like the real numbers). Hence, virtually all decision >> problems >> are undecidable.
> I'm curious to know - can you explain how you know (perhaps via a formal >or informal proof) that there are uncountable many decision problems?
For each real number x, consider the decision problem D(x) defined as follows:
Given rational number r, decide whether r < x.
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.