How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Question

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?

Thanks

Answer 1

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.

Answer 2

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 \}$$