1
$\begingroup$

Are there countable infinte decision problems or uncountable infinite?

Thank you

$\endgroup$
2
  • 4
    $\begingroup$ A decision problem on a alphabet (i.e. non-empty finite set) $\Sigma$ is some subset $P\subseteq \Sigma^*$ (i.e. $P\in\mathcal P(\Sigma^*)$). So it's uncountable (because $\mathcal P(\Sigma^*)$ is). $\endgroup$
    – xavierm02
    Jan 20, 2017 at 14:23
  • $\begingroup$ @xavierm02 Please post answers as answers, not as comments. $\endgroup$ Jan 20, 2017 at 15:05

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.