Header Ads

How to show that a function is not computable?

11:56 PM
Question Detail: 

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a Pumping lemma?
Asked By : user5507
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11181

Answered By : Ran G.

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist?

[notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$]

Undecidable languages do exist

There are some languages that no Turing machine can decide. The argument is simple: there are "only" countably many $(\aleph_0)$ different TMs, but uncountably many $(\aleph)$ different languages. Thus there are at most $\aleph_0$ decidable languages, and the rest (infinitely many) are undecidable. Further reading:

In order to put our hand on a specific undecidable language, the idea is to use a technique named diagonalization (Georg Cantor, 1873) which was originally used to show that there are more real numbers than integers, or in other words, that $\aleph > \aleph_0$.

The idea for constructing the first undecidable language is simple: we list all Turing machines (which is possible since they are recusively enumerable!), and create a language that disagrees with each TM on at least one input.

$$ \begin{array}{c|ccccc} & \varepsilon & 0 & 1& 00 & \cdots \\ \hline M_1 & \color{red}{1} & 0 & 1 & 0 & 1 \\ M_2 & 0 & \color{red}{1} & 0 & 0 & 0 \\ M_3 & 0 & 0 & \color{red}{0} & 1 & 0 \\ \vdots & & & & \ddots & \end{array} $$

In the above, each row is one TM and each column is one input. The value of the cell is 0 if the TM rejects or never halts, and 1 if the TM accept that input. We define the language $D$ to be such that $D$ contains the $i$-th input if and only if the $i$-th TM does not accept that input.

Following the table above, $\varepsilon \notin D$ since $M_1$ accepts $\varepsilon$. Similarly, $0\notin D$, but $1\in D$ since $M_3$ does not accept $1$.

Now, assume $M_k$ decides $D$ and look up line $k$ in the table: if there is $1$ in the $k$-th column, then $M_k$ accepts that input but it is not in $D$, and if there is a $0$ there, the input is in $D$ but $M_k$ does not accept it. Therefore, $M_k$ doesn't decide $D$, and we reached contradiction.

Now for your question. There are several ways to prove that a language is undecidable. I'll try to touch the most common ones.

1. Direct proof

The first method, is to directly show that a language is undecidable, by showing that no TM can decide it. This ususally follows the diagonalization method shown above.

Example.

Show that the (complement of the) diagonal language $$\overline {L_D} = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}$$ is undecidable.

Proof.
Assume $\overline {L_D}$ is decidable, and let $M_D$ be its decider. There are two cases:

  1. $M_D$ accepts $\langle M_D \rangle$: but then, $\langle M_D \rangle \in L(M_D)$ so $\langle M \rangle \notin \overline {L_D}$. So this can't happen if $M_D$ decides $\overline {L_D}$.
  2. $M_D$ does not accept $\langle M_D \rangle$: so $\langle M_D \rangle \notin L(M_D)$ and thus $\langle M \rangle \in \overline {L_D}$. But if it is in $L_D$, $M_D$ should have accepted it, and we reached contradiction again.

2. Closure properties

Sometimes we can use closure properties to show some language is not decidable, based on other languages we already know not to be decidable.

Specifically, if $L$ is not decidable (we write $L\notin R$), then also its complement $\overline{L}$ is undecidable: if there is decider $M$ for $\overline{L}$ we could just use it to decide $L$ by accepting whenever $M$ rejects and vice versa. Since $M$ always halts with an answer (it is a decider), we can always invert its answer.

Conclusion: The diagonal language ${L_D} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \}$ is undecidable, $L_D \notin R$.

A similar argument can be applied by noting that if both $L$ and its complement $\overline{L}$ are recursively enumerable, both are decidable. This is particular useful if we want to prove that a language is not recursively enumerable, a strong property than undecidability.

3. Reducing from an undecidable problem

Usually, it's quite difficult to directly prove that a language is undecidable (unless it is already constructed in a "diagonal" fashion). The last and most common method for proving undecidability is to use another language which we already know to be undecidable. The idea is to reduce one language to another: to show that if one is decidable, then the other must also be decidable, but one of them is already known to be undecidable which leads to the conclusion that the first one is also undecidable. Read more about reductions in "What are common techniques for reducing problems to each other?".

Example.

Show that the diagonal language $$HP = \{ \langle M,x \rangle \mid M \text{ halts on } x \}$$ is undecidable.

Proof.
We know that $L_D$ is undecidable. We reduce $L_D$ to $HP$ (this is denoted $L_D \le HP$), that is, we show that if $HP$ was decidable we could use its decider to decide $L_D$, which is a contradiction.

The reduction works by converting a candidate $w$ for $L_D$ (i.e. an input for any potential decider/acceptor for $L_D$) to a candidate $w'$ for $HP$ such that $w\in L_D$ if and only if $w' \in HP$. We make sure that this conversion is computable. Thus, deciding $w'$ tells us whether or not $w\in L_D$, so if we can decide HP we would be also able to decide $L_D$.¹

The conversion is as follows. Take some $w=\langle M \rangle$, and output $w'=\langle M' , \langle M \rangle\rangle$,² where $M'$ is a TM that behaves just like $M$, but if $M$ rejects, then $M'$ goes into an infinite loop.

Let's see that $w,w'$ satisfy the requirements.
If $w\in L_D$, it means that $M$ halts and accepts the input $\langle M\rangle$. Therefore, $M'$ also halts and accepts the input $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \in HP$.
On the other hand, if $w\notin L_D$ then $M$ either rejects or never halts on $\langle M\rangle$. In both cases $M'$ will go into an infinite loop on $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \notin HP$, and we are done showing that $w\in L_D$ if and only if $w'\in HP$, and have thus shown that $HP\notin R$.

Further reading: many examples for reductions and proving undecidablility of languages can be found via the tag.

  1. There are some more restriction on the reduction to be valid. The conversion itself must be computable, and well defined for any input.

  2. An input of $HP$ looks like $\langle M,x\rangle$, where $M$ is a TM and $x$ is some string. So here we choose the string $x$ to be an encoding of the machine $M$, which is just some string..

4. Rice's Theorem

"So every time we wish to prove $L$ is undecidable, we need to reduce $L_D$ (or $HP$) to it? Isn't there any shortcut?"

Well, in fact, there is. This is Rice's Theorem.

The theorem says that many languages that have a certain structure, are undecidable. Because all these languages have this certain structure, we can do the reduction once and apply it to any language that admits a similar structure.

The theorem is formally stated in the following way,

Theorem (Rice). Given a property $\emptyset \subsetneq S \subsetneq RE$, the following language $L_S$ is undecidable $$ L_S = \{ \langle M \rangle \mid L(M) \in S \} $$

The set $S$ is a subset of languages in $RE$; we call it a property because it describes a property of the accepted language $L(M)$. All the TMs whose language satisfies this property belong to $L_S$.

For instance, $S$ can be the property that the accepted language $L(M)$ contains exactly two words:

$$S_2 = \{ L \mid |L| =2 , L \in RE\}.$$ In this case $L_{S_2}$ is the set of all TMs whose language consists of exactly two words: $$L_{S_2} = \{\langle M \rangle \mid L(M) \in S\} = \{\langle M \rangle \mid |L(M)|=2\}.$$

The property can be very simple, but it cannot be all the RE languages, or none of the RE languages. If $S=\emptyset$ or $S=RE$ then the property is said to be trivial, and the induced $L_S$ is computable. An example for a simple $S$ is one the contains only a single language, say $S_{complete}=\{ \Sigma^*\}$. Note that although $S$ contains only a single language, there are infinitely many machines $M$ whose language is $\Sigma^*$, so $L_{S_{compete}}$ is infinite, and undecidable.

The theorem is very powerful to prove undecidability of many languages.

Example.

The language $L_\emptyset = \{ \langle M \rangle \mid M \text{ never reaches the accepting state} \}$, is undecidable

Proof.
We can write $L_\emptyset$ as $\{ \langle M \rangle \mid L(M)=0 \}$, that is $L_\emptyset=L_S$ for the property $S=\{ L \in RE, |L|=0\}$. This is a non-trivial property (it includes the language $L=\emptyset$, but does not include, for instance, the language $L=\{1, 11, 111,\ldots\}$. Therefore, by Rice's Theorem, $L_\emptyset$ is undecidable.

We now prove the theorem. As mentioned above, we are going to show a reduction from $HP$ to $L_S$ (for any arbitrary non-trivial $S$).

Proof.
Let $S$ be a non-trivial property, $\emptyset \subsetneq S \subsetneq RE$. We show $HP \le L_S$, that is, we reduce $HP$ to $L_S$ so that if we can decide $L_S$ we will be able to decide $HP$ (which we know to be impossible, therefore, $L_S$ cannot be decidable). In the proof below we assume that the empty language is not part of $S$, that is $\emptyset \notin S$. (if the empty language is in $S$, an equivalent proof works on the complement property $\overline S = RE \setminus S$, I'll omit the details). Since $S$ is nontrivial, it includes at least one language; let's call that language $L_0$ and assume $M_0$ is a machine that accepts $L_0$ (such machine exists, since $S$ includes only languages in RE).

Recall that in such a reduction (See section 3 above), we need to show how to convert an input $w$ for $HP$ into an input $w'$ for $L_S$ so that $$ w\in HP \quad \text{ if and only if }\quad w' \in L_S$$

Let $w=(\langle M \rangle, x)$, we convert it into $w'=\langle M' \rangle$ where the description of the machine $M'$ (on an input $x'$) is the following:

  1. Run $M$ on $x$.
  2. If Step 1 above halts, run $M_0$ on $x'$ and accept/reject accordingly.

We see that this conversion is valid. First note that it is simple to construct the description of $M'$ given $w=(\langle M \rangle, x)$.

If $w\in HP$, then $M$ halts on $x$. In this case, $M'$ proceeds to step 2, and behaves just like $M_0$. Therefore its accepted language is $L(M')=M_0\in S$. Therefore, $w'=\langle M' \rangle \in L_S$.
If $w\notin HP$ then $M$ loops on $x$. This case, $M'$ loops on any input $x'$ — it gets stuck in step 1. The language accepted by $M'$ in this case is empty, $L(M')=\emptyset \notin S$. Therefore, $w'=\langle M' \rangle \notin L_S$.

4.1 The Extended Rice Theorem

Rice's theorem gives us an easy way to show that a certain language $L$ that satisfies certain properties is undecidable, that is, $L \notin R$. The extended version of Rice's theorem allows us to determine whether the language is recursively-enumerable or not, that is, determines whether $L \notin RE$, by checking if $L$ satisfies some additional properties.

Theorem (Rice, extended). Given a property $S \subseteq RE$, the language $$ L_S = \{ \langle M \rangle \mid L(M) \in S \} $$ is recursively-enumerable ($L_S \in RE$) if and only if all the following three statements jointly hold

  1. For any two $L_1, L_2 \in RE$, if $L_1 \in S$ and also $L_1 \subseteq L_2$ then also $L_2 \in S$.
  2. If $L_1\in S$ then there exists a finite subset $L_2 \subseteq L_1$ so that $L_2 \in S$.
  3. The set of all finite languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L\in S$).

Proof.
This is an "if and only if" theorem, and we should prove both its directions. First, we show that if one of the conditions (1,2,3) does not hold, then $L_S \notin RE$. After that we will show that if all three conditions hold simultaneously, then $L_S \in RE$.

If (1,2) hold, but (3) does not, then $L_S \notin RE$.
Let's assume that $L_S \in RE$, and we'll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M_L$ that accepts only the words in $L$, and now we run the machine of $L_S$ on $M_L$ (remember - we assumed $L_S\in RE$, so there is a machine that accepts $L_S$!). If $L\in S$ then $\langle M_L \rangle \in L_S$ and since $L_S\in RE$, its machine will say yes on the input $\langle M_L \rangle$, and we are done.

If (2,3) hold, but (1) does not, then $L_S \notin RE$.
We assume that $L_S \in RE$ and we'll show that we have a way to decide $HP$, leading to a contradiction.

Because condition (1) doesn't hold, there is a language $L_1 \in S$ and a superset of it, $L_2 \supseteq L_1$ so that $L_2 \notin S$. Now we are going to repeat the argument used in Section 4 to decide $HP$: given an input $(\langle M \rangle,x)$ for $HP$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ or otherwise, its language is $L_2$. Then, we can decide $HP$: either $M$ halts on $x$, or the RE-machine for $L_S$ accepts $M'$; we can run both in parallel and are guaranteed that at least one will halt.

Let's give the details of constructing $M'$ (on input $x'$):

  1. Do the following in parallel:
    1.1 run $M$ on $x$.
    1.2 run the machine of $L_1$ on $x'$
  2. If 1.2 halts and accepts - accept.
  3. If 1.1 halts: run the machine of $L_2$ on $x'$.

Why does this work? If $(\langle M \rangle,x)\notin HP$ then 1.1 never halts, and $M'$ accepts exactly all the inputs that are being accepted at step 1.2, so $L(M')=L_1$. On the other hand, if $(\langle M \rangle,x)\in HP$ then, at some point step 1.1 halts and $M'$ accepts exactly $L_2$. It may happen that $1.2$ accepts beforehand, but since $L_1 \subseteq L_2$, this doesn't change the language of $M'$ in this case.

If (1,3) hold, but (2) does not, then $L_S \notin RE$.
Again, we will assume $L_S\in RE$ and show that $HP$ becomes decidable, which is a contradiction.

If condition (2) doesn't hold, then for any $L_1\in S$, all its finite subsets $L_2 \subseteq L_1$ satisfy $L_2 \notin S$ (note that $L_1$ must be infinite, since $L_1\subseteq L_1$). As in the above, in order to decide $HP$ for a given input $(\langle M \rangle,x)$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ and some finite $L_2$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M'$ we constructed. The machine $M'$ (on input $x'$) does:

  1. Runs $M$ on $x$ for $|x'|$ steps.
  2. If $M$ halts during step 1 – reject
  3. Otherwise, run the machine of $L_1$ on $x'$.

It holds that, if $(\langle M \rangle,x)\in HP$, then at some point, say after 1000 steps, $M$ halts on $x$. Therefore, step 1 will halt on (and reject) any input $x'$ of length $>1000$. Therefore, in this case, $L(M')$ is finite. Also note that $L(M') \subseteq L_1$, and in particular, by our assumptions on the invalidity of condition (2), we have that $L(M) \notin S$.

On the other hand, if $(\langle M \rangle,x)\notin HP$, then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L(M)=L_1$ and in particular, $L(M)\in S$.


We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L_S$, that is, $L_S \in RE$. In other words, we need to show a machine $M_S$ so that for any input $\langle M \rangle$ for which $L(M) \in S$, the machine accepts this input, $M_S(\langle M \rangle) \to \textsf{accept}$.

Here is how the machine $M_S$ behaves (on input $\langle M \rangle$):

  1. Let $M_{\text{enum }S}$ be the machine that enumerates all the finite languages in $S$, guaranteed by condition (3).
  2. Run the following in parallel (by dovetailing, see e.g., this and this) for $i=1,2,...$
    2.1 Run $M_{\text{enum }S}$ until it outputs the language $L_i$
    2.2. Check if $M$ accepts all the words of $L_i$ (run $M$ on these words, again in parallel).
    2.3. If for some $i$, $M$ accepts all the words of $L_i$ – accept.

Why does it work? If $L(M) \in S$ then it has a finite subset $L_j \in S$, and once $M_{\text{enum }S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L(M) \notin S$ it cannot be accepting all the words in $L_i$ for any $i=1,2,...$. Indeed, by condition (1), any $L' \supseteq L_i$ is also in $S$, so if $M$ accepts all the words in $L_i$ for some $i$, then $L(M)\supseteq L_i$ and thus $L(M) \in S$, in contradiction.

Finally, note that the following is a simple (and very useful) corollary of the above:

Corollary (Rice, extended). Given a non trivial property $S \subsetneq RE$, so that $\emptyset \in S$, the language $$ L_S = \{ \langle M \rangle \mid L(M) \in S \} $$ is not recursively-enumerable, that is, $L_S \notin RE$.

Post a Comment

No comments

Subscribe to: Post Comments ( Atom )
Powered by Blogger.