Oliver Wong 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?
Formally, a decision problem is a subset of strings over some alphabet, say the binary alphabet. There are uncountably many such subsets.