24 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 ...
user avatar
17 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 ...
user avatar
  • 29.1k
15 votes
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 ...
user avatar
  • 141k
15 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 ...
user avatar
  • 70.9k
11 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 ...
user avatar
9 votes
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 ...
user avatar
8 votes
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, ...
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 ...
user avatar
8 votes

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

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Fancy answer We need to show that the set $$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$ is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to $$\exists n, m \...
user avatar
  • 28.2k
7 votes
Accepted

What is the meaning of undecidability in Rice Theorem?

Undecidable means not decidable. Undecidable problems may or may not be semi-decidable. To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many ...
user avatar
7 votes

undecidable problem and its negation is undecidable

Note that the overwhelming majority of problems fit the criterion you're looking for: both the problem and its complement are not semi-decidable. This is because there are only countably many semi-...
user avatar
7 votes

undecidable problem and its negation is undecidable

Here are some natural examples: The language of all Turing machines halting on all inputs, sometimes denoted TOT. This language is $\Pi_2^0$-complete. The language of all Turing machines halting on ...
user avatar
7 votes

Is the language of TMs that decide some language Turing-recognizable?

Of course, this depends on what you exactly mean. Do you mean, all the machines that decides a specific language? e.g., $$ L = \{ \langle M \rangle \mid M \text{ decides the language } A\}$$ then, ...
user avatar
  • 20.4k
7 votes
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 ...
user avatar
  • 70.9k
7 votes

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 ...
user avatar
  • 13.2k
7 votes

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 ...
user avatar
  • 4,747
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 ...
user avatar
  • 9,612
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 ...
user avatar
  • 34.1k
6 votes

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 ...
user avatar
  • 28.2k
6 votes

Language is recursive, hence recursively enumerable

Depending on what definitions you use, the proof can be trivial. We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $...
user avatar
6 votes
Accepted

Is the language of TMs that decide some language Turing-recognizable?

This language is usually known as TOT, the language of machines computing total functions. It is $\Pi_2$-complete, and in particular is neither recognizable nor co-recognizable.
user avatar
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 ...
user avatar
6 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. ...
user avatar
  • 28.2k
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$,...
user avatar
5 votes
Accepted

True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

It is not true that every language is recursively enumerable ("type 0"). Proof 1. Every RE language is semi-decided by some Turing machine. There are only countably many Turing machines (each one can ...
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 ...
user avatar
  • 51
5 votes

Function is recursive iff its graph is recursively enumerable

In order to prove your claim, you need to prove two things: If a function is recursive then its graph is r.e. If the graph of a function is r.e. then it is recursive. Let's see what you have to do ...
user avatar
5 votes

A language is Turing recognizable iff it is a projection of a decidable language

There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., ...
user avatar
  • 20.4k
5 votes
Accepted

Language is recursive, hence recursively enumerable

One possible definition of recursively enumerable (most likely the one used by your instructor) is that it is the domain of a partial function. In Turing Machine terms, that means the following ...
user avatar
  • 19.1k

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