proving if a Turnig machine accept a string is undecidable

Question

I have seen the proof of

ATM = {〈M,w〉 | M is a TM and M accepts w} is undecidable.

initially we build another Turing machine

H with input <M,w> it accept if M accept w otherwise reject then we make another Turing machine

D which on input <M>
1.run H on <M,<M>>
2.output the opposite of what H outputs. 

That is if H accepts reject and if H reject accept

I dont understand how is it possible that a Turing machine as input gets its own description and then reject it! Can you please explain it?

Answer 1

I'm not sure where exacltly you got stuck, so I'll more or less try to reiterate your question, hopefully filling any gaps.

The idea is, that we want to show that ATM is undecidable, i.e. that there is no TM H, that when given any another TM M and any other input w to this TM M as input can decide if the TM M will accept input w.

To show that such a TM H doesn't exist we make the ASSUMPTION such a machine H exists. Which at least with enough phantasy might not seem to be a much too unreasonable guess.

The next Idea is to just by deducing the consequences the existence of such a TM H would have lead our argumentation the to a contradiction. Thus proving that our initial assumption such a TM H might exist must be wrong. Meaning there doesn't exist any TM H following our specification given above.

So now on to the tricky part: As we assumed there exists a TM H that when given ANY TM M and ANY input w to this TM M as input can decide wether M will accept w nobody can forbid us to just feed a description of the machine M itself als input w into M itself. We even made the assumption we might use ANY input.

As you already stated above the idea of feeding any machine as input into another doesn't seem to bee too easy to accomplish, we will rather try to encode the description of the second TM on our first TM's tape.

At a first glance it might not seem to clear if it is really possible to be able to encode any TM on the tape, but in fact it is possible. One of the possible schemes to accomplish this goes by the name of Gödelisierung named after the mathematician Kurt Gödel.

The encoding itself is also often refered to as Gödelnumber.

Given our TM H that when given the description of ANY TM M and ANY input w to M as input decides wether M will accept w, using our freedom already mentioned above we will simply use TM M's description as input to itself.

Thus constructing a TM H' that when given any description of a TM M as input will decide if TM M working on its own description as input will accept or not.

As you hopefully see starting from our assumption a TM H as specified above we haven't done any "forbidden" move and we surely won't do, if we use our newly constructed TM H' to construct a TM D that when given ANY TM M as input wil just return the opposite output than our machine H'.

This new TM D, when given the description of ANY TM M as input will accept > if the M doesn't accept its own description as input and reject > if the TM M accepts its own description as input.

As you can see we still have the freedom to feed any (description of a) TM M as input into D, so happily using our freedom once again nobody can ever forbid to use the description of the TM D itself as input.

According to our construction D works on ANY TM M as input, so it surely has to be able to work on itself.

But exactly here comes the twist. As a matter of fact to determine the outcome ouf our run of D on its own description as input we just have to possibilities: D will either accept or reject.

Now let's examine both cases:

In case D accepts it's own description as input by our construction this would mean D would have to reject and vice versa. Remember it was the TM H' that acceptet ANY TM that accepted it's own description as input and we just inverted it in our construction.

Thus leading us to the odd fact that D would have to reject its own description as input if and only if it accepted it.

As this obviously can't be posssible you have to find the root of the error we made in our construction. Following the whole path we made up again this leads us our initial deduction that there was a TM H able to decide for ANY TM M and ANY input w if M will accept w, which was implied by our assumption that ATM was decidable.

Answer 2

The input to a machine has no special status, and doesn't impose any requirements. A machine is free to reject itself. :)

Cause i don't feel like building a Turing machine, here's an oversimplified example in Java (which is close enough to Turing completeness that it serves to illustrate):

class SelfReject {
    public boolean equals(Object other) {
        ...
    }

    public boolean accepts(Object input) {
        return (!this.equals(input));
    }
}

An object of this type would accept any input but an object equal to itself.