24
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 different subsets of $\mathbb{N}$ but only countably many Turing machines that could act as enumerators.) So any subset of $\mathbb{N}$ that you already ...
17
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 enumerate the members of this set. If such an algorithm existed, we could use this to solve the halting problem with inputs $x,M$, with the following algorithm:...
16
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 x and a machine H, we can't say whether the machine H halts or not on input x.
No, that's not what it says. The halting problem is the computational problem of ...
15
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 true of its complement. Why? The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at ...
13
I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.
10
It is completely possible for both $L$ and $\overline{L}$ to be unrecognizable. For example, for any unrecognizable $M$, the language $L = 0M + 1\overline{M}$ over $\Sigma = \{0,1\}$ has this property (why?).
10
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 example. Suppose that $L$ is recursively enumerable (there is a Turing machine enumerating all words in $L$) and also co-recursively enumerable (there is a Turing ...
9
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 in parallel and accept/reject as soon as $w$ appears in one of the enumerations. $\Box$
So, if you can prove that $L$ is not recursive but its complement is RE, ...
8
Yes, a recursively enumerable language may be either decidable or undecidable. To see this, you ust look at the definitions of the terms.
A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-...
8
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, perhaps confusingly, partial computable is a larger class of functions: every computable function is partial computable. One could reduce the confusion at the cost ...
8
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 is clearly partially computable, but it has no computable extension, since you could use any such extension to solve the halting problem (why?).
Exercise for ...
8
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 an effective procedure that, given some (finite) input, produces some (finite) output, after some (finite number of) steps. To simplify matters further, we ...
7
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 \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$
where $T$ is Kleene's predicate and $U$ the associated output function.
In words, the ...
7
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 problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems....
7
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-decidable problems but there are uncountably many problems.
For an example, let $H$ be the halting problem for Turing machines and let $\cal{M}$ be the class of ...
7
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 infinitely many inputs, sometimes denoted INF. This language is also $\Pi_2^0$-complete.
The language of all Turing machines halting on arbitrarily long inputs, ...
7
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, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).
But if you mean, any language, ...
7
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 your reasoning is sound, one of your assumptions has to be faulty. What you assume is, paraphrased:
Assuming semi-decider $H$ for $L$, I can enumerate $L$ in ...
7
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 if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$.
Given $x$, ...
7
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 not then the TM may not stop. Thus PCP is an RE language. Recognizability should not be confused with decidability.
We can do the same with deterministic TM ...
7
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 many undecidable but recursively enumerable languages whose complements are not recursively enumerable. These languages are subset of $\Sigma^*$ and hence are ...
6
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 the domain of $g$.
Cruicially, there is no requirement that $A'$ be a proper subset of $A$. Thus, every total function is also a partial function.
This is ...
6
The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- another proof may still work!
The problem is that flipping the result of a TM only works ...
6
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 $S$ and rejects the non-members of $S$. Such a Turing machine is called a decider of the set.
One definition of the recursively enumerable sets is that $S$...
6
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.
6
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 they have uncountably many subsets, but there are only countably many Turing recognizable languages.
6
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.
The standard example of an immune set is as follows. Consider the set
$$P = \{\langle m, n\rangle \mid n > 2 m \land n \in W_m \},$$
where $\langle {-}, {-}\...
5
$L_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE ...
5
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 every input in finite time. We also say it's computable.
A formal language is undecidable if and only if it is not decidable.
A formal language is ...
5
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 be coded as a finite string, or an integer) but there are uncountably many languages. Therefore, there are uncountably many languages that are not RE.
Proof ...
Only top voted, non community-wiki answers of a minimum length are eligible