Questions tagged [uncountability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
1k views

Can a recursive language be uncountable?

Does there exist a recursive language $L$ whose cardinality is uncountable? I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to ...
2
votes
2answers
820 views

Is there a non-recursive and uncountable language L?

Does there exist a non-recursive language, L, such that the cardinality of L is uncountable? I would really like an explanation as to why this question is true or false because at the moment, I have ...
1
vote
2answers
311 views

Why are pushdown automata countable? [closed]

I began a chapter in a textbook on computational theory where they begin to talk about decidable languages. The problems in this section are pretty confusing and I honestly don't know how to begin ...
6
votes
1answer
1k views

Where am I wrong?: “countability” and “recursive enumerability”

I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong ...
1
vote
1answer
161 views

Countability union of all finite and countably infinite sequences over finite alphabet

Is the set of all finite and countably infinite sequences over $\{0,1\}$ countable? From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=...
1
vote
1answer
102 views

Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$

This is my take : Epsilon ---> 1 0 --> 2 01 ---> 3 10 ---> 4 11 ---> 5 001 ---> 6 010 ---> 7 . . . So therefore we can count them. But based on this video : https://www.youtube.com/watch?v=...
2
votes
1answer
622 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.