1
$\begingroup$

Let N be a non-deterministic TM with Σ as its alphabet, and we define the next language:

UNIQUE(N) = {w∈Σ*|w has an unique accepting path on N}.

w can have another computational paths on M, but none that result in the accept state.

Is the language UNIQUE(N) is Turing-recognizable, for every non-deterministic TM N?

If so, I need to prove it. If not, I need to give an example of a non-deterministic TM N, so that UNIQUE(N) is not Turing-recognizable.

Following my intuition, I tried to build N such that UNIQUE(N) is ATM^c, but it didn't work out. For the other direction I don't have an idea.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider a (deterministic) TM $D$ that recognizes the language $\text{HALT}_{\text{TM}} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$, and let $N$ be a (nondeterministic) TM that, given input $x$, at the beginning of its operation guesses to accept $x$ immediately or branch into another run where it (deterministically) simulates the run of $D$ on $x$ and answers the same.

It is not hard to see that $N$ has exactly two runs on any input $x$, one that is accepting, and the other simulates the run of $D$ on $x$. In particular, $N$ accepts all inputs. However, the set of inputs $x$ that $N$ has a single run on, are exactly the inputs that $D$ does not accept. Hence, $\text{UNIQUE}(N) = \overline{L(D)} = \overline{\text{HALT}_{\text{TM}}} \notin \text{RE}$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.