# Turing machine - Reducible

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,

• Are you asking for help understanding the problem, or for help understand the particular solution to the problem you've been given? Commented Apr 13, 2018 at 23:49
• Thank you for the response, sir. I think I need help for both problem and solution. Also, the diagram is quite different from what I learned, and it would help if any clarification is provided. @HenningMakholm
– user551192
Commented Apr 13, 2018 at 23:55
• Hello @HenningMakholm maybe understanding the particular part of solution, especially diagram would help.
– user551192
Commented Apr 14, 2018 at 2:11

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.

• Thank you for your answer. I am wondering if there is a reference for simple introduction to this kind of concept and deductibility .
– user551192
Commented Apr 14, 2018 at 22:41