snippetCritical
How to show that a function is not computable? How to show a language is not computably enumerable?
Viewed 0 times
showcomputablycomputablefunctionlanguageenumerablethathownot
Problem
I know that there exists 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?
Similarly, how can we show a language is not recursively enumerable?
Similarly, how can we show a language is not recursively enumerable?
Solution
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.
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:
$\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.
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.
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
[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:
- "Why are there more non-computable functions than computable ones?" and
- "Why are the total functions not enumerable?".
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.
- 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:
- $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}$.
- $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.
- 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.
- 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
Context
StackExchange Computer Science Q#11181, answer score: 60
Revisions (0)
No revisions yet.