Reduction from ATM.
Assume that EVEN TM is decidable with decider MT.
We now show how to build, given a ⟨M, w⟩ a machine description ⟨M'⟩ that satisfies the following faithfulness condition.
If M accepts w then M' accepts every even-length string
If M does not accept w then M' does not accept every even-length string
On input x
 If x is an **odd-length** string then accept
 Else simulate M on w and answer what M answered.
Obviously M' satisfies the faithfulness condition.
Here is a decider for ATM.
On input ⟨M, w⟩
1. Build ⟨M'⟩
2. Run MT on input ⟨M'⟩
3. Answer what MT answered.

So I have this solution the the problem, what I don't understand is why ⟨M'⟩ checks for odd length first then accepts right away? this doesnt make sense to me

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 16 '18 at 11:09
  • 1
    $\begingroup$ Why the downvote? We have a specific question here, that's about as good as homework-style questions get. $\endgroup$ – Raphael Feb 16 '18 at 11:10
  • 1
    $\begingroup$ @Raphael Indeed, I was wondering about that as well. For once, this question is focused on a single step (handling odd-length strings). It is not the usual problem / solution dump with a general "explain everything". It could be improved, sure, but it is decent. $\endgroup$ – chi Feb 16 '18 at 16:58
  • $\begingroup$ I did try to make it as short as possible and to the point. Turns out that condition I was having trouble with is useless and can be simply removed. $\endgroup$ – crystyxn Feb 16 '18 at 19:59

The idea is that for this reduction, we want the resulting TM to give us exactly the answer to $A_{TM}$, and the focus here isn't M' but much rather what happens when we call the decider (which you call MT) on M' instead.

To go through this in detail, bear in mind the reduction is considered valid if we can someone manage construct a machine that can decide $A_{TM}$ which we know derives a contradiction. Consider the one that you provided:

  1. Let's say that D(M') accepts. This means that M' doesn't accept any odd inputs at all, so that means we need to feed M' even inputs for it to accept. This also means that when given an even input $x$, it'll always discard $x$ and run M(w) instead, so it must be that M(w) always accepts. Which means we can know that $<M,w>$ $\in A_{TM}$, or that M will halt on w.

  2. Now the opposite direction. Let's say that D(M') rejects. This means that M' doesn't accept when any even input. But if that's the case, this must mean that M(w) doesn't accept at all, this should follow from the same idea as (1).

So as an overview, we're saying, assuming that we can decide $EVEN_{TM}$, it would then be possible construct a decider for $A_{TM}$. The important thing to note here is that the focus is on: (a) creating a new machine M' for the decider based on the inputs to $<M, w>$ for $A_{TM}$, and (b) making sure that the decider accepts M' if and only if $<M, w> \in A_{TM}$ to derive a contradiction.


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.