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 ...
- 80.3k
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 ...
- 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 ...
D.W.♦
- 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 ...
- 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 ...
- 270k
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 ...
- 80.3k
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, ...
- 80.3k
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 ...
- 270k
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 ...
- 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 \...
- 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 ...
- 80.3k
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-...
- 80.3k
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 ...
- 270k
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, ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 $...
- 80.3k
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.
- 270k
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 ...
- 270k
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.
...
- 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$,...
- 270k
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 ...
- 80.3k
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 ...
- 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 ...
- 270k
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., ...
- 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
...
- 19.1k
Only top scored, non community-wiki answers of a minimum length are eligible