# Tag Info

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 ...
• 80.3k

### 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 ...
• 29.1k
Accepted

### undecidable problem and its negation is undecidable

Consider the following language: $$L_2 = \{(M_1,x_1,M_2,x_2) : \text{M_1 halts on input x_1 and M_2 doesn't halt on input x_2}\}.$$ $L_2$ is undecidable and not semi-decidable, and same is ...
• 141k
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 ...
• 70.9k
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 ...
• 270k
Accepted

### How to prove that a language is not recursively enumerable

Here are two methods. Consider the complement Theorem. If a language $L$ and its complement are both RE, they are both recursive. Proof. Decide whether $w\in L$ by enumerating $L$ and its complement ...
• 80.3k
Accepted

### Is it possible to obtain a total function by composition of partial functions?

The theorem should be read as "If you compose computable functions, you get a computable function; if you compose partial computable functions, you get a partial computable function." Note that, ...
• 80.3k
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 ...
• 270k

### Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"/convergence?

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 ...
• 4,676

• 20.4k
Accepted

### Is the language TMs that accept finite languages Turing-recognizable?

If that method worked, semi-decidability would always imply decidability for infinite languages (note how you don't need any property of $L$ to make the proof work), which we know is not true. Since ...
• 70.9k

### set of Kolmogorov-random strings is co-re

We want to show $\overline{R_c}\in RE$. $\overline{R_c}=\left\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|<|x| \right\}$, i.e. $x$ is not a Kolmogorov-random string ...
• 13.2k

### Is Post's correspondence problem recognizable?

We can recognize acceptable inputs of PCP by exhaustively checking all valid possibilities (preferably by non-deterministic TM). That is it!. If the input is acceptable then the TM will stop, if it is ...
• 4,747

### 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 ...
• 9,612
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 ...
• 34.1k

### Is it possible to obtain a total function by composition of partial functions?

This is a confusion about terminology: A function $f : A \to B$ is total if it is defined everywhere on $A$. A function $g : A \to B$ is partial if it is defined on a subset $A' \subseteq A$, called ...
• 28.2k

• 20.4k