2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ You styled the problem and prompt for proof as a block quote. Please provide who created both and where it was published first. $\endgroup$
    – greybeard
    Dec 23, 2023 at 10:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aditya
    Dec 23, 2023 at 10:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ > 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. $\endgroup$
    – Aditya
    Feb 4 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.