Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}.

How can I prove that this is undecidable? I have considered trying to build the ATM proof assuming this language. Language A can cover acceptance under even steps but how would I cover acceptance under uneven steps? Language A would reject in that case. How would you go about trying to build the proof via this path?

Another thing I wonder is if Rice's theorem covers this language. Would this be considered a functional property? Could I use it to prove the undecidability of this language?


  • 1
    $\begingroup$ Have you tried to do a mapping reduction from A_TM? Where did you get stuck? As for Rice's theorem - do you know what the definition of a functional (or "semantic") property is? Does this language admit such a property? $\endgroup$ – Shaull Jul 7 '16 at 14:45
  • $\begingroup$ I did try mapping a reduction from A_TM. I made A_TM simulate A with w, and accept if it accepts, this however is not enouph and I dont know what else to add. Maybe if I can assume language A, I can construct A' that does the same but for uneven number of steps, this would allow me to complete the proof via this way. $\endgroup$ – Ricardo Ferreira da Silva Jul 7 '16 at 14:54
  • $\begingroup$ "the ATM proof " -- what do you mean? A reduction from A_TM? $\endgroup$ – Raphael Jul 7 '16 at 23:35
  • $\begingroup$ ad Rice: nope. See here and here. $\endgroup$ – Raphael Jul 7 '16 at 23:36
  • $\begingroup$ Yes a reduction from A_TM as in I assume what I want to prove is undecidable is decidable and I try to make the algorithm for A_TM decidable, thus reaching a contradiction. $\endgroup$ – Ricardo Ferreira da Silva Jul 8 '16 at 8:27

This is a bit of a nit-picky question, since you really need to pay attention to the parity of the number of steps you TM does.

We'll show that the problem is undecidable by a reduction from $A_{TM}$. There are many ways to construct such a reduction. In my opinion, the following is the least technical.

Given input $(M,w)$ for $A_{TM}$, we will construct a new output $(M',\epsilon)$, such that $M$ accepts $w$ iff $M'$ accepts $\epsilon$ within an even number of steps.

We construct $M'$ as follows: given input $x$, if $x\neq \epsilon$, then $M'$ rejects.

Otherwise, if $x=\epsilon$, $M'$ works as follows: simulates the run of $M$ on $w$. If $M$ accepts, it clears the tape by going to the rightmost non-blank cell, and then writes blanks all the way to the left. It then simulates $M$ again, erases the tape again in exactly the same manner, and accepts.

If $M$ rejects, then $M'$ rejects as well.

The idea here is that if $M$ accepts $w$, then the operation of $M'$ on $\epsilon$ is to simulate $M$ on $w$ twice. Therefore, it will take an even number of steps.

Proving the correctness and computability of this procedure is not hard.

  • $\begingroup$ In this proof you are assuming A_TM is decidable right? $\endgroup$ – Ricardo Ferreira da Silva Jul 7 '16 at 15:28
  • $\begingroup$ No. If we'd assume that A_TM is decidable, we would have assumed a contradition, and would be able to prove anything. We show a reduction from A_TM, which essentially means that if your language was decidable (co-recognizable, actually), then A_TM would also be, which we know is not the case. $\endgroup$ – Shaull Jul 7 '16 at 18:37

In short, if you could decide membership in the language $A$, then you could decide whether a Turing machine accepts a word. Because TM acceptance is undecidable, this proves that a decider for $A$ can't exist.

Here's a machine that uses a subroutine for $A$ in order to solve the acceptance problem. Given a machine and word $\langle M, w\rangle$, design a new machine $M^\prime$. The new machine is exactly the same as $M$, except that it has an extra step in the beginning where it does nothing. (e.g. $M^\prime$ has a new starting state $q_0^\prime$. Initially, the machine reads the tape, prints nothing, doesn't move, and transitions into the start state $q_0$ of $M$.)

Now, if $M$ rejects $w$ then so does $M^\prime$. Otherwise, they both accept $w$, and $M^\prime$ takes one more step than $M$— so one of the two machines takes an even number of steps to accept.

So, if we could decide whether a TM accepts a word in an even number of steps, we could decide whether $M$ accepts $w$. Just test $\langle M, w\rangle$ and $\langle M^\prime, w\rangle$ and return ACCEPT if either one takes an even number of steps to accept, or else return REJECT.

Rice's theorem doesn't apply because "accepting in an even number of steps" is not a property that languages have, but a property that specific Turing machines have. (Two Turing machines can have the same language, but one of them might belong to $A$ and the other one not.) Rice's theorem applies just to languages of the form

$$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property }p \}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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