All Questions
Tagged with uncountability undecidability
6 questions
6
votes
2
answers
2k
views
How to determine if a set is countable or uncountable?
When I am presented with a problem of finding whether or not the given set is countable, I cannot figure out how to determine it or prove it. The general approach is to compare it with $\mathbb{N}$, ...
- 141
0
votes
1
answer
113
views
Doubt regarding Cantor's diagonalization argument [closed]
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.
I understand the overall argument but have a problem regarding one caveat mentioned in my ...
- 111
1
vote
1
answer
2k
views
Is L={<M>|M is a TM and L(M) is uncountable} decidable?
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 ...
user87413
2
votes
1
answer
2k
views
Is there any undecidable language that is countable?
All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.
- 21
3
votes
2
answers
3k
views
Decidability of Unary Languages / One-to-One Mapping
I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power ...
- 33
3
votes
1
answer
971
views
Undecidability and Countability
This question is prompted by Undecidable unary languages (also known as Tally languages)
How does the countability of a language imply (un)decidability?
- 213