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

### 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.9k
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 ...
• 72.8k
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 ...
• 278k

### 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. ...
• 31k
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 ...
• 278k

### 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 ...
• 5,776

### 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 ...
• 2,516

### 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,877
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 ...
• 39.1k

### 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 ...

### 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$,...
• 278k
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",...
• 9,877
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 ...
• 72.8k
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 ...
• 7,176
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 ...
• 39.1k
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 ...
• 16k

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

• 82.1k
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,...$ ...
• 9,877
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 ...
• 628
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 ...
• 82.1k
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 ...
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 ...
• 278k