Are there countable infinte decision problems or uncountable infinite?
Thank you
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityAre there countable infinte decision problems or uncountable infinite?
Thank you
Uncountable. In fact you can see a decision problem P as a language L (the words corresponds with the inputs that are accepted by P) on alphabet Σ. A language can be encoded by an infinite binary string generating all the strings in Σ* in lexical order and associating 1 if the current string belongs to L, 0 otherwise.
The set of infinite binary strings S is uncountable infinite. Let's assume it is countable infinite. Then we can find an association between natural numbers and the strings in S, and list them. But if we take the string composed of the complement of the bits on the diagonal, then we obtain a new infinite binary string which belongs to S but is not in the list. Contraddiction.
So the set of languages (and the set of decision problems) is uncountable infinite.