Questions tagged [uncountability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
3answers
3k views

Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
0
votes
1answer
107 views

Question about non recursively enumerable language [duplicate]

Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable? In other words, let $R$ be the set of languages (including languages ...
0
votes
1answer
961 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 ...
1
vote
1answer
73 views

What is the relation between countability and recursive enumeration? [duplicate]

Does recursive enumeration implies countability? Does countability implies recursive enumeration? I believe the first implication holds but not sure about the second. A good example would suffice.
2
votes
2answers
1k views

Are all finite strings over some infinite alphabet countable?

Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?
0
votes
3answers
672 views

Are the sets of all finite automata and pushdown automata countable?

So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering ...
1
vote
1answer
92 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=...
4
votes
1answer
65 views

Is repetition the origin of countability?

The original question was "Do all non-regular languages have an uncountable number of strings?". How can someone prove that..? I am squeezing my head but I can't figure it out. And the other side ...
2
votes
1answer
395 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.
3
votes
2answers
949 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 ...
-2
votes
1answer
390 views

Is every countably infinite language recursive?

We'll say the alphabet for the languages is finite, say {0,1}.
2
votes
2answers
553 views

Can a regular language have uncountably many strings?

Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no,...
2
votes
2answers
743 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 ...
4
votes
3answers
441 views

Showing that the number of primitive-recursion programs for each function is countably-infinite

Problem Statement Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$ Yes, this is a homework question. My ...
0
votes
2answers
390 views

Countability of a binary tree

Problem: We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable. My attempt: A set is countable if it is ...
1
vote
2answers
877 views

Number of finite strings over a countably infinite alphabet

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
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 ...
1
vote
1answer
100 views

Is the union of finite and infinite sequences over alphabet of length 1 countable?

Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well? I understand this is similar a question to the one of finite and countably infinite ...
1
vote
1answer
132 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
votes
1answer
1k views

Deciding Countability of Languages

Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable (a) Set of all languages over $\Sigma$ (b) Set of all regular languages over $\Sigma$ (c) Set of ...
1
vote
1answer
380 views

Are all languages generate by Turing machines countable?

Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
0
votes
1answer
341 views

Prove that the set of all total functions is countable [closed]

I'm stuck on a theory/set proof question: $S$ is the set of all total functions $f : \{0, 1\} \to \mathbb{N}$ (natural numbers), prove that S is countable. I have found a sample solution already ...
1
vote
2answers
292 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 ...
2
votes
1answer
315 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?
2
votes
2answers
2k views

Is the set of all valid C programs countable?

Is the set of all syntactically valid C programs countable or uncountable?
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 ...
2
votes
1answer
304 views

How to prove “The power set of a countable set must be uncountable”?

I'm not sure if this statement is correct, but my friend said so. The problem arose from this T/F question: Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $...
-2
votes
3answers
439 views

If set of TM's is not countable?

I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?
3
votes
2answers
1k views

Cantor's diagonal method in simple terms?

Could anyone please explain Cantor's diagonalization principle in simple terms?
8
votes
2answers
1k views

Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?

COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...