Skip to main content
Share Your Experience: Take the 2024 Developer Survey
26 votes
Accepted

Are there any countable sets that are not computably enumerable?

Are there any examples of countable sets that are not enumerable? Yes. All subsets of the natural numbers are countable but not all of them are enumerable. (Proof: there are uncountably many ...
David Richerby's user avatar
19 votes

Are there any countable sets that are not computably enumerable?

Yes, every undecidable (not semi-decidable) language has this property. For example, consider the set $L = \{(x,M) \mid M \text{ does not halt on input } x \}$. Suppose we have an algorithm that can ...
Joey Eremondi's user avatar
16 votes
Accepted

Why is the halting problem semi-decidable?

Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity. Halting problem says that for a given input ...
Raphael's user avatar
  • 72.5k
12 votes
Accepted

Dovetailing in Turing Machines?

Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time. Why is dovetailing useful? Here is one ...
Yuval Filmus's user avatar
8 votes
Accepted

Partial recursive function with no total recursive extension

Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function ...
Yuval Filmus's user avatar
8 votes

Definition of an immune set

Standard construction of a (co-c.e.) immune set Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory. ...
Andrej Bauer's user avatar
  • 30.8k
8 votes

Why doesn't infinite run time violate Turing completeness? Shouldn't "completeness" include halting?

You do not yet understand what Turing completeness means. Turing completeness is the ability to perform arbitrary finite computations. To simplify matters, we say an arbitrary finite computation is ...
reinierpost's user avatar
  • 5,694
7 votes

Is the Rice Theorem applicable for these problems?

Rice's theorem cannot be used to show the undecidability of these two languages. Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property ...
Hans Hüttel's user avatar
  • 2,516
7 votes

Are there any countable sets that are not computably enumerable?

In computability theory we deal with subsets of $\Sigma^*$, where $\Sigma = \{0,1\}$. This language is countably infinite, and so any subset $L \subseteq \Sigma^*$ is countable. Furthermore, there are ...
fade2black's user avatar
  • 9,837
7 votes
Accepted

How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

An approach for the undecidability Let $G$ be a context-free grammar. We can add to $G$ new context-free generation rules that employs new variables without using any variables in $G$ (except the ...
John L.'s user avatar
  • 39k
6 votes

Does Every Recognizable language has a subset not Recognizable?

No, finite languages don't have subsets which aren't Turing recognizable. However, infinite languages (Turing recognizable or not) always have subsets which are not Turing recognizable, simply because ...
Yuval Filmus's user avatar
6 votes

How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

Let $G$ be a context-free grammar over an alphabet $\Sigma$ with initial variable $S$. Create a new grammar $G'$ with a new initial variable $S'$, a new variable $A$, and transitions $S' \to S \mid A$,...
Yuval Filmus's user avatar
5 votes

Definition of an immune set

An interesting example of immune set is the set of random numbers in Kolmogorov complexity. The Kolmogorov complexity $k(n)$ of a number $n$ is the smallest $i$ such that $\varphi_i(0) = n$. The idea ...
Andrea Asperti's user avatar
5 votes

The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

The answer you gave is right, but I'd like to stress the relationship between the two terms. A formal language is decidable if and only if there exists an algorithm which correctly accepts or rejects ...
dan p's user avatar
  • 51
5 votes
Accepted

The Church-Turing-Thesis in proofs

A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable",...
fade2black's user avatar
  • 9,837
5 votes
Accepted

Proof that total computable functions are not enumerable

$g$ is total computable by definition. By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable. $1$ certainly is. $+$ certainly is. The concatenation of $+$ and $f$ is computable by ...
Raphael's user avatar
  • 72.5k
5 votes
Accepted

Determining if given languages are regular or recursively enumerable

Your intuition is entirely correct; this solution is nonsense. $L_1$ isn't a regular language; it's not even a decidable language, by Rice's Theorem, and also not recognizable (aka recursively ...
Draconis's user avatar
  • 7,138
5 votes
Accepted

Is it decidable whether a Turing machine M will reach state q on input s?

Do we ever take into consideration a word with infinite length during such analysis? Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can ...
John L.'s user avatar
  • 39k
5 votes
Accepted

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

It depends on the reduction. Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an ...
Nathaniel's user avatar
  • 15.7k
4 votes

How to prove that a language is not recursively enumerable

Some common techniques include: We start by picking any $L'$ which is known to be non RE, e.g. we let $L'$ to be the complement of the halting problem. Then we prove the m-reduction $L' \leq_m L$. If ...
chi's user avatar
  • 14.6k
4 votes

Closure of Turing-recognizable languages under homomorphism

A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L_1, L_2 \in \mathcal{L}$ we also have $L_1 \cdot L_2 \in \mathcal{L}$. Here, $A \cdot B = \{ v \...
Raphael's user avatar
  • 72.5k
4 votes

Proof that total computable functions are not enumerable

The problem really is in how you're approaching the proof by contradiction. You're objecting to one conclusion ("$g$ is computable and total") by drawing a different conclusion ("$g$ isn't total ...
Noah Schweber's user avatar
4 votes

is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

We can write a computer program that will enumerate all halting computer programs. It seems that you are happy to accept accumulating the output of program into a (potentially infinite) set. Thus, you ...
Arno's user avatar
  • 3,123
4 votes

Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: diagonalization. Any time we have a class of decidable languages for which we have a "...
Noah Schweber's user avatar
3 votes
Accepted

Given language consisting Turing machines is decidable or not?

In other words, $L=\{\langle M \rangle:L(M)\notin \{\phi,\Sigma^*\}\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very ...
dave's user avatar
  • 628
3 votes
Accepted

How can I prove that there is a decidable language which is not in P?

Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question ...
David Richerby's user avatar
3 votes
Accepted

Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

Maybe that will help ? https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf Page 42 ...
Gal Rettig's user avatar
3 votes
Accepted

which of the following languages are Recursively Enumerable?

$B$ is r.e, but $A$ is not. You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s_1, s_2,...$ ...
fade2black's user avatar
  • 9,837
3 votes
Accepted

Unrecognizable languages relationship to NP-hard languages

There are NP-hard languages arbitrarily high in the arithmetical hierarchy. To answer your specific question, the complement of the halting problem is NP-hard and it's in $\mathrm{coRE}\setminus\...
David Richerby's user avatar
3 votes
Accepted

Enumerable disjoint subsets whose union is equal to the union of the sets

This answer assumes that enumerable means recursively enumerable. Here is an enumerator for $C$: Run enumerators for $A,B$ in parallel. Whenever the enumerator for $A$ outputs a word, check whether ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible