# Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?

I am asking this in the context of the following question:

Let N be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where the finite control is in the state p, the head scans the tape a, and $$\delta (p, a)$$ offers multiple (two or more) possibilities, where p is neither the accept state nor the reject state. Consider the following language $$\text{DILLEMA}_{ALL} = \{\langle N\rangle| N \text{ is a NTM which faces a dilemma at least once on each input}\}$$ Prove that $$\text{DILLEMA}_{ALL}$$ is not recursively enumerable

Here is how I have attempted this problem

To prove that $$\text{DILLEMA}_{ALL}$$ is not recursively enumerable, we prove that $$\bar{A}_{TM} \le_m \text{DILLEMA}_{ALL}$$.

Here is how we construct the proof for reducibility.

For any input $$\langle M, w\rangle$$ we have to return an output $$N$$ for our reducibility function.

1. Construct a deterministic Turing machine N which gets an input $$x$$ and run $$M$$ on $$w$$.
2. If $$M$$ accepts, accept $$x$$ ie. $$L(N) = \Sigma^*$$
3. If $$M$$ rejects, take any state $$q$$ in the Turing machine $$N$$ which is not accept or reject state and copy the succeeding computational graph from this state. Rename the copied states to say $$q_1$$ and $$q_2$$ and make a non-deterministic transition from $$q$$ to $$q_1$$ and $$q_2$$.
4. Output $$\langle N \rangle$$.

Proof of correctness:

1. When $$w \not \in L(M) \Leftrightarrow \langle N \rangle \in \text{DILLEMA}_{ALL}$$
2. When $$w \in L(M) \Leftrightarrow \langle N \rangle \not \in \text{DILLEMA}_{ALL}$$

Thus it has been proven that $$\bar{A}_{TM} \le_m \text{DILLEMA}_{ALL}$$ and hence $$\text{DILLEMA}_{ALL}$$ is not recursively enumerable.

What I have essentially done is to introduce non-determinism in a deterministic turing machine by adding a compatible transition which doesn't affect the behaviour of the machine other than making it non-deterministic.

My professor however disagrees with my proof, and claims that I did not include the case where the turing machine neither rejects nor accepts ie. loops forever in my proof of correctness for reducibility. I believe that the case is implicit since if $$M$$ loops forever then $$N$$ is obviously not giving any output ie. it is also looping forever.

Could anyone please validate my proof or explain my professor's criticisms in more detail since I was not able to understand his reasoning? I couldn't find any mention of explicitly writing the looping case even for non recursively enumerable languages in textbooks or anywhere else.

• You styled the problem and prompt for proof as a block quote. Please provide who created both and where it was published first. Commented Dec 23, 2023 at 10:36
• @greybeard I don't understand what you mean by this. The question was set by my professor for the term examination and the solution was created by me. I want to know what is wrong with my proof. I used a block quote to highlight the problem and distinguish it from my solution. Commented Dec 23, 2023 at 10:49

Not only your professor is correct, but also the reduction is not well-written. Specifically, you did one of the following (and both are wrong):

• The reduction simulates the run of $$M$$ on $$w$$, and then decides which $$N$$ to output: this cannot be done as the machine that computes the reduction may not halt.

• The reduction always halts and outputs a description of a machine $$N$$ that operates as follows. On input $$x$$ for $$N$$, $$N$$ neglects $$x$$ and simulates the run of $$M$$ on $$w$$. Then, depending on what happens during the simulation, you change the definition of $$N$$ on the fly. This is not well-defined, as the state-space of $$N$$ depends on how it behaves on its input $$x$$ -- you see now that you have a circular definition. You should define the nondeterministic state q in the machine $$N$$, regardless of what happens in the simulation of $$M$$ on $$w$$, meaning the nondeterministic state is always defined in $$N$$, and the question is whether it is not reached on some inputs only when $$M$$ accepts $$w$$.

Here is how to do it properly, and how to fix the problem of non-halting:

The reduction: on input $$\langle M, w\rangle$$, the reduction outputs $$\langle N\rangle$$, where $$N$$ is a nondeterministic machine that operates as follows. $$N$$ has a single nondeterministic state $$q_{N}$$ from which it guesses to move to $$q_{rej}$$ or move to $$q_{acc}$$: $$\delta(q_{N}, \gamma) = \{ \langle q_{acc}, \gamma, R \rangle, \langle q_{rej}, \gamma, R \rangle \}$$, forall $$\gamma \in \Gamma$$. Then, on input $$x$$, $$N$$ computes $$|x|$$ and simulates the run of $$M$$ on $$w$$ for $$|x|$$ steps, if during the simulation $$M$$ did not accept $$w$$, then $$N$$ moves to the state $$q_{N}$$. Otherwise, if during the simulation $$M$$ accepted $$w$$, then $$N$$ moves to $$q_{reject}$$.

Clearly, for all $$x$$, $$N$$ faces a dilemma when it runs on $$x$$ only if it reaches the state $$q_{N}$$, which happens only when $$M$$ does not accept $$w$$ within $$|x|$$ steps.

For the correctness: if $$\langle M, w\rangle \in \overline{A_{TM}}$$, then $$M$$ does not accept $$w$$, in particular, $$M$$ does not accept $$w$$ within $$|x|$$ steps for all $$x$$. Hence, for all $$x$$, the run of $$N$$ on $$x$$ reaches $$q_{N}$$, and thus $$\langle N\rangle\in DILEMMA_{ALL}$$. Conversely, if $$\langle M, w\rangle\in A_{TM}$$, then $$M$$ accepts $$w$$ after $$t$$ steps. Then for all $$x$$ with $$|x|\geq t$$, $$N$$ moves to $$q_{rej}$$ and never visits $$q_{N}$$, and so $$\langle N\rangle \notin DILEMMA_{ALL}$$.

Notes:

1- If we allow the simulation to not halt, then on input $$x$$, $$N$$ does not accept or reject, and we do not know whether it will accept in the future or not halt. Thus, it never reaches a dilemma, but we want it to reach a dilemma in this case -- for this reason we bound the number of steps when we simulate.

2- The main thing is whether we visit $$q_{N}$$ or not. The fact that we sometimes accept or reject in some cases is not important.

• > This cannot be done as the machine that computes the reduction may not halt. Yes in that case there is no N given as output either. It will only decide if M halts. Commented Feb 4 at 10:27