# Questions tagged [uncountability]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
82 views

### What's wrong with this “proof” that $\mathbb{R}$ is enumerable?

The fake proof: We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it. But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable. We ...
274 views

### Does infinite length strings lead to uncountable languages?

This answer says: We can have uncountable languages only if we allow words of infinite length. So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
99 views

### How is the set of functions from ${\{a,b\}}$ to $N$ countable?

Assume a set of functions from ${\{a,b\}}$ to $N$ Where $N$ is the set of Natural numbers. Let us assume that the size of $N$ is $n$. i.e $|N|=n$ The first element $a$ have $n$ choices for mapping....
187 views

### Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

I came across following facts: Set of finite languages over a finite alphabet is countable. Set of languages over finite alphabet is uncountable. I believe proof of this will be similar to ...
72 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 ...
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 ...
247 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 ...
1k 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 ...
120 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.
3k 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?
908 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 ...
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=...
70 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 ...
634 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.
1k 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 ...
469 views

### Is every countably infinite language recursive?

We'll say the alphabet for the languages is finite, say {0,1}.
805 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,...
828 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 ...
544 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 ...
497 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 ...
1k 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?
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 ...
110 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 ...
165 views

547 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?