Given that
- Membership Problem is known undecidable
- Membership Problem: "Given a Turing machine M and string w, does M accept input w?"
- Emptiness Problem: "Given a Turing machine M, is L(M) = ∅ ?"
- L(M): the language accepted by the Turing machine, that is, the set of all words w that when given as input to M eventually enter an accepting state.)
Solution: Reduce the Membership Problem to the Emptiness Problem.
However, I cannot understand the diagram from [Link to the image].
Please, help me understand this problem.
Thank you,
The solution proposed aim to show that the Turing machine described by the second diagram is total (i.e. terminate on all inputs, assuming that you have the total machine $D_E$.
I that were the case then you would have build a total Turing machine that computes the membership problem, which is absurd.
The diagrams are quite simple actually. They basically represent Turing machines as black-boxes that take some inputs and get some outputs (represented by the wires getting inside (inputs) and outside (outputs) of the boxes).
External boxes represent the Turing Machines you want to define, namely the $M_w$ and $D_A$, while the smaller boxes inside the bigger one represent sub-Turing machines that are composed to get the bigger Turing machine (here a sub-Turing machine is the same as a sub-routine in a programming language).
So each smaller box in the bigger ones represent the call to a Turing machine with the input given by the label in the input wire of this smaller box.
To each smaller box can have either one output wire o two depending on whether it provides a string or a "yes or no" answer.
If the smaller box returns just a string then its output-string is passed as input to another box (i.e. another Turing machine) or it could be used as the output of the machine being described (but that is not the case in the diagram you posted). The output string is put as a label of the output wire.
If the smaller box returns a "yes or no/accept or reject/..." answer it has two output wires. Each wire can be thought as an activation wire that can be used to activate another sub-Turing machine with a specified input (input which is the label of the input wire of this sub-Turing Machine) or it just become the yes-no/acc-rej answer of the Turing machine being defined.
I hope this helps.