patternMinor
What approaches are most useful when proving uncomputability of a given function?
Viewed 0 times
provingwhatarefunctionuncomputabilityusefulwhenapproachesgivenmost
Problem
I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows:
I've applied (or rather, tried to apply) both the above techniques to some reductions, two of which I now state here (for illustrating the limitations of my approach):
-
If whenever a TM M accepts a string w $\in$ ${\{0,1\}}^$, it also accepts $w^R$, the TM M is said to possess property R. ($w^R$ is the string obtained by reversing $w$ i.e. $(110)^R$ is $011$). Let $R: {\{0,1\}}^ \rightarrow \{0,1\}$ be defined as follows: $R(\alpha) = 1$ if $M_\alpha$ possesses property $R$, and $R(\alpha) = 0$ otherwise. Prove that $R$ is uncomputable.
-
Let $B: {\{0,1\}}^$ x $ {\{0,1\}}^ \rightarrow \{0,1\}$ be defined as follows:
$B(\alpha,x) = 1$ if $M_\alpha$ writes a non-blank symbol on its output tape while computing input $x$, $B(\alpha,x) = 0$ otherwise. Prove that function $B$ is uncomputable.
For problem 1, I tried reducing the uncomputable function $UC$ to $R$, but the reason I couldn't quite complete the reduction is because $R$ is a property of the Turing Machine, not dependent on any input instance, where $UC$ depends on the output of a specific instance $M_\alpha(\alpha)$. Also, for both $R(\alpha)$ = 0
- Reduction, from a known uncomputable function (such as $UC(\alpha)$, the uncomputable function as proved by Cantor's diagonalization argument in Chapter 1 of the book "Computational Complexity" by Sanjeev Arora and Boaz Barak, or $HALT(\alpha, x)$, which is nothing but the function in the Halting problem), to F. If such a reduction is possible, it can be argued that F is uncomputable as otherwise, the problems that are proved to be uncomputable would become be computable as well.
- Proof by contradiction, in which one shows that if there is a TM M that computes F, it would lead to some sort of inconsistency in either the M's output, or the functions evaluated value.
I've applied (or rather, tried to apply) both the above techniques to some reductions, two of which I now state here (for illustrating the limitations of my approach):
-
If whenever a TM M accepts a string w $\in$ ${\{0,1\}}^$, it also accepts $w^R$, the TM M is said to possess property R. ($w^R$ is the string obtained by reversing $w$ i.e. $(110)^R$ is $011$). Let $R: {\{0,1\}}^ \rightarrow \{0,1\}$ be defined as follows: $R(\alpha) = 1$ if $M_\alpha$ possesses property $R$, and $R(\alpha) = 0$ otherwise. Prove that $R$ is uncomputable.
-
Let $B: {\{0,1\}}^$ x $ {\{0,1\}}^ \rightarrow \{0,1\}$ be defined as follows:
$B(\alpha,x) = 1$ if $M_\alpha$ writes a non-blank symbol on its output tape while computing input $x$, $B(\alpha,x) = 0$ otherwise. Prove that function $B$ is uncomputable.
For problem 1, I tried reducing the uncomputable function $UC$ to $R$, but the reason I couldn't quite complete the reduction is because $R$ is a property of the Turing Machine, not dependent on any input instance, where $UC$ depends on the output of a specific instance $M_\alpha(\alpha)$. Also, for both $R(\alpha)$ = 0
Solution
There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this.
Note that the proof by reduction is just a special case of a proof by contradiction; assuming that the function is computable leads to a proof that some other problem is computable, which is a contradiction if there's already a proof that the other problem is not computable.
Your first problem can immediately be shown to be uncomputable due to Rice's Theorem. Briefly, Rice's Theorem states that for any non-trivial semantic property of TMs, detecting whether a given TM has the property is undecidable. Semantic means the property depends only on the language accepted by the TM (all TM's accepting the same language have the property, or all do not have the property, regardless of the specific implementation). Non-trivial simply means that there do exist languages that have the property, and languages that don't. So one way to solve this problem is to simply recognise that "for all strings w accepted by M, the reverse of w is also accepted by M" is a non-trivial semantic property and invoke Rice's Theorem. That may not be the most satisfying way to solve your problem if you're doing this to learn though (although the proof of Rice's Theorem is quite accessible; it's essentially a very generalised reduction from the Halting Problem).
For your reduction proofs, remember that you can "cheat". You are assuming the existence of a solver (call it P) for the problem you're trying to prove undecidable, and show that if you had that you could solve the Halting Problem. This means your reduction can presume that P "just works" by black-box magic, regardless of whether it seems possible. In particular, you do not need to care that the machines you construct to feed to P halt or do anything at all useful; only that they cause P to accept/reject in a way that can be used to solve the Halting Problem (or some other undecidable problem, but I found the Halting Problem to be very productive when I was doing these sorts of exercises at uni).
For example, one of my most enjoyable exercises in my undergraduate Theory of Computation course was proving that it as undecidable to detect whether a TM ever attempted to move the tape head left from the left-most cell of the tape (in the model we were using this would cause the tape head to simply remain in the left-most cell). I did this by showing that for an arbitrary TM M you could construct a machine that was in fact guaranteed not to halt on any input, but would attempt to move left from the left-most cell if-and-only-if M halted on the same input.
So what you need to do to prove $R$ uncomputable by reduction is find some undecidable problem P, such that you can transform an arbitrary instance of P's input into a TM that has the property R if-and-only-if the original input to P should be accepted (or rejected; the negative works too).
Similarly for problem 2, the obvious (to me) thing to do is to take an arbitrary TM M, and transform it into a machine M' that halts exactly when M writes something on the output tape, and is guaranteed not to halt if M never writes something on the output tape. Don't get hung up on whether M or M' halts; you're not planning to run either of them, only to run your hypothesized solver for problem 2 with M' as input.
Note that the proof by reduction is just a special case of a proof by contradiction; assuming that the function is computable leads to a proof that some other problem is computable, which is a contradiction if there's already a proof that the other problem is not computable.
Your first problem can immediately be shown to be uncomputable due to Rice's Theorem. Briefly, Rice's Theorem states that for any non-trivial semantic property of TMs, detecting whether a given TM has the property is undecidable. Semantic means the property depends only on the language accepted by the TM (all TM's accepting the same language have the property, or all do not have the property, regardless of the specific implementation). Non-trivial simply means that there do exist languages that have the property, and languages that don't. So one way to solve this problem is to simply recognise that "for all strings w accepted by M, the reverse of w is also accepted by M" is a non-trivial semantic property and invoke Rice's Theorem. That may not be the most satisfying way to solve your problem if you're doing this to learn though (although the proof of Rice's Theorem is quite accessible; it's essentially a very generalised reduction from the Halting Problem).
For your reduction proofs, remember that you can "cheat". You are assuming the existence of a solver (call it P) for the problem you're trying to prove undecidable, and show that if you had that you could solve the Halting Problem. This means your reduction can presume that P "just works" by black-box magic, regardless of whether it seems possible. In particular, you do not need to care that the machines you construct to feed to P halt or do anything at all useful; only that they cause P to accept/reject in a way that can be used to solve the Halting Problem (or some other undecidable problem, but I found the Halting Problem to be very productive when I was doing these sorts of exercises at uni).
For example, one of my most enjoyable exercises in my undergraduate Theory of Computation course was proving that it as undecidable to detect whether a TM ever attempted to move the tape head left from the left-most cell of the tape (in the model we were using this would cause the tape head to simply remain in the left-most cell). I did this by showing that for an arbitrary TM M you could construct a machine that was in fact guaranteed not to halt on any input, but would attempt to move left from the left-most cell if-and-only-if M halted on the same input.
So what you need to do to prove $R$ uncomputable by reduction is find some undecidable problem P, such that you can transform an arbitrary instance of P's input into a TM that has the property R if-and-only-if the original input to P should be accepted (or rejected; the negative works too).
Similarly for problem 2, the obvious (to me) thing to do is to take an arbitrary TM M, and transform it into a machine M' that halts exactly when M writes something on the output tape, and is guaranteed not to halt if M never writes something on the output tape. Don't get hung up on whether M or M' halts; you're not planning to run either of them, only to run your hypothesized solver for problem 2 with M' as input.
Context
StackExchange Computer Science Q#4577, answer score: 7
Revisions (0)
No revisions yet.