I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:
I start with a decider H, that has an input
<M,w> where M is a Turing Machine and w is a string, so I have the following:
H(<M,w>)=accept if M accepts w rejects if M rejects w
all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:
------------- D that is a TM | ----- | | | H | | | |____| | |___________|
So it says that D calls H to determine what M would do if the input is M, it means something like:
Now it says that it should do the opposite this decider H, it means that:
H(M,<M>)=reject if M accepts <M> accepts if M rejects <M> ---------(1)
and this procedure can be generalized for D like:
D(<M>)=accept if M does not accept <M> ----------(2) reject if M accept <M>
I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?
The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?
At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?