4
$\begingroup$

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):

  1. 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.

  2. 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.

$\endgroup$

4 Answers 4

7
$\begingroup$

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.


$\endgroup$
0
1
$\begingroup$

Perhaps another way to prove Q1 is the following:

1) we can automatically build the transition table of a $TM_{(m,x)}$ that on every input $w$ simply adds the fixed string $\#m\#x$ at its end, and bring the head to the intial tape position (the final tape content of $TM_{(m,x)}(w)$ is $w\#m\#x$);

2) we can explicitly build a $TM_{sim}(w\#m\#x)$ that simulate $TM_m$ on input $x$ and if it halts output $w^R$

Now, suppose that there is a Turing machine $TM_R(\alpha)$ that decide if $TM_\alpha(w)=w^R$ for all $w$.

Given $m$ and $x$, we can find the $\alpha$ that correspond to the TM with a transition table that is the concatenation of the transition table of $TM_{(m,x)}$ and the transition table of $TM_{sim}$

But by construction: $TM_R(\alpha) = 1$ if and only if $TM_\alpha(w) = w^R$ for all w, if and only if $TM_{sim}(w TM_{(m,x)})=w^R$ for all w, if and only if $TM_m(x)$ halts; i.e. we would be able to solve $HALT(m,x)$.

$\endgroup$
0
$\begingroup$

I think problem 2 is decidable.
We shall prove that $B$ is computable by describing a 2-tape $TM M$ that decides it:
$M$ will simulate $M_\alpha$ on $x$ and will keep on its 2nd tape the configurations (= state, head position and symbols currently on tape) $M_\alpha$ has been in. Each time $M_\alpha$ "moves", $M$ will check if this configuration has been visited.
$M$ will also write on it's 2nd tape the states in which $M_\alpha$ last visited a new blank cell (one that has NEVER been visited before) to the right and to the left of the input (2 different lists).
We will name this $LBSL$ (Last Blank State Left [of original input]) and $LBSR$. Additionally, each time $M_\alpha$ visits a non blank cell [= the original input] $M$ will delete $LBSL,LBSR$.

If $M_\alpha$ writes a symbol on the tape, $M$ will accept.
If $M_\alpha$ accepts or rejects, $M$ will reject.
If $M_\alpha$ revisits a configuration $M$ will reject.
If $M_\alpha$ visits a blank cell to the right of the input, which it never visited before, and the state of $M_\alpha \in$ $LBSR$, $M$ will reject. Same for left of input and $LBSL$.

We will prove that $M$ rejects the input $\iff$ $M_\alpha$ will never write anything on $x$:
$\implies$ Let us assume $M$ has rejected some input.
1.If this was because $M_\alpha$ halted, obviously $M_\alpha$ wouldn't have written anything.
2.If $M_\alpha$ revisited a configuration: $M_\alpha$ is deterministic and thus will repeat the steps between the first and 2nd visit, and will keep doing this forever.
Now for the messy part:
3. If $M_\alpha$ visited a new cell, in the same state, without going through the input in between then it has only read blank chars between this two configurations. Thus $M_\alpha$ will repeat the same steps, because it will again read only blanks. Notice that the new blank cell is further away from the input. This means it will once again visit a new blank cell in the same state and will never write anything.

For the other part of the iff, we need to show that either 2 or 3 will happen on any machine that never writes anything for input x and never halts.
Notice that after visting a new blank cell $M_\alpha$ will either:
$I$ visit a new blank space some time in the future, and because the number of states is finite this will in some point result in situation 3.
$II$ $M$ will use bounded space from now on (because $I$ does not happen), and thus will repeat a configuration, resulting in situation 2.

I admit this is a messy construction & proof, and it is possible I have missed something on the way.

EDIT: I forgot to mention why M (the decider) halts on every input, but this should be obvious. Also, I know I did not answer your question. I think Ben did an excellent job at that. I just felt that the decider for B should be mentioned (assuming I did not miss anything). Maybe I should have opened a new question for that? I'm not sure.

$\endgroup$
0
$\begingroup$

Here's the general approach I used, which I'm hoping would be useful for similar types of problems on deciding uncomputability of functions using TMs. There are 2 types of such functions (as far as I've faced!):

  1. Functions which decide properties of the language accepted by the Turing Machine supplied as input, e.g. Problem 1 in my question, and doesn't depend on the behaviour of that TM on any specific input instance.

  2. Functions which take a tuple $<\alpha, x>$, whose output depends on the behaviour of $M_\alpha$ on input $x$.

For Type 1 problems (given a function $F(\alpha)$ which predicts some property of $M_\alpha$), use the following mechanism:

  1. Assume $M_\beta(\alpha)$ to be the TM that computes $F(\alpha)$.
  2. Construct a TM $M_\gamma(w)$, which would accept only a select set of inputs $w \in \{0,1\}^*$, such that $F(\gamma) = 1$ iff $M_\alpha(x)$ returns 1, for any input $x$.
  3. Evaluate $M_\beta(\gamma)$. If $M_\beta(\gamma) = 1$, it implies $M_\alpha(x) = 1$, otherwise $M_\beta(\gamma) = 0 \Rightarrow > M(\beta)$ can predict if $M_\alpha(x)$ would be accepted or not. That is clearly not possible, hence $M_\beta$ cannot exist.

Note: The real trick in Type 1 problems is to design the behaviour of the TM $M_\gamma$, such that it

  1. Rejects most inputs (so as to simplify the construction), and
  2. Accepts only particular input cases so as to cause $M_\beta(\gamma)$ to be true, only when the output of $M_\alpha$ is true. (For problem 1, I made $M_\gamma$ reject all inputs other than 01 and 10. For 01, it returned 1, while for 10, it simulated the behaviour of $M_\alpha(x)$, and returned whatever that returned.)

For Type 2 problems, where the output of $F(\alpha, x)$ depends on the output/operation of a TM $M_\alpha$ on a specific input $x$, use the following approach:

  1. Assume $M_\beta(\alpha, x)$ to be the TM that computes $F(\alpha, x)$.
  2. Construct a TM $S$ which on input $<\alpha, x>$, does the following:
    1. Construct a TM $M_\gamma(w)$ such that $M_\beta(\gamma, w) = 1$ iff $M_\alpha(w)$ returns 1.
    2. Run $M_\beta$ on <$\gamma, x$>, and return its output.

Thus, it can be seen that the TM $S$ accepts only when $M_\alpha$ accepts, which is not possible!

Note:, For problem 2, I made $M_\gamma$ to be a 2 Tape TM that on input $w$, simulates $M_\alpha$ on $w$ using the first tape, and write a non-blank symbol on its second tape if $M_\alpha$ accepts!

$\endgroup$
1
  • $\begingroup$ I'm pretty sure that the answer can be improved/made more concise - I would welcome such changes to it! $\endgroup$
    – TCSGrad
    Sep 17, 2012 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.