1
$\begingroup$

Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable?

My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is not decidable, how can I prove that using reducibility?

$\endgroup$

1 Answer 1

10
$\begingroup$

This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it.

(I initially gave the entire answer away, but edited it out after considering a bit.)

$\endgroup$

Your Answer

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