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:
- 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 and $R(\alpha)$ = 1, it is possible that $M_\alpha$ can go on indefinitely for some inputs!
For problem 2, I tried reducing the function $HALT$ to $B$ (thus attempting to make a TM that computes $HALT(\alpha,x)$ by using the output of a TM $M_\beta$ that computes $B$). But here as in problem 1, it is possible that for both outputs of $M_\beta(\alpha,x)$, the TM $M_\alpha$ may not halt at all on input $x$!
So, I'm stumped here - I understand intuitively why these functions should be uncomputable (No TM should be able to predict whether another TM would halt/output anything on any possible input), I'm not quite able to derive a concrete proof! So, I really want to understand what approaches am I missing here, or are there holes in the current approaches that I've tried so far!
Note: For self-containment, I'm stating what are the functions UC and HALT here as well:
$UC: {\{0,1\}}^* \rightarrow \{0,1\}$:
$UC(\alpha) = 0$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ = 1
$UC(\alpha) = 1$, otherwise.
$HALT: {\{0,1\}}^*$ x $ {\{0,1\}}^* \rightarrow \{0,1\}$:
$HALT(\alpha, x) = 1$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ halts on input $x$.
$HALT(\alpha, x) = 0$, otherwise.