The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
30 views

Determine whether the given set is countable [migrated]

Given the set $V = $ { $w$ | $w$ is an infinite sequence in the form of $a_0a_1a_2\ldots$ with $a_i \in \{0,1,2\}$ for all $i \ge 0$ } Determine if V is countable. I'm assuming V is countable, and ...
2
votes
1answer
227 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
35 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
49 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 ...
-1
votes
1answer
39 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
36 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
70 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 ...
1
vote
2answers
137 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
79 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?
1
vote
2answers
289 views

Is the set of all valid C programs countable?

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

Cantor's diagonal method in simple terms?

Could anyone please explain Cantor's diagonalization principle in simple terms?
4
votes
1answer
373 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 ...