1
$\begingroup$

I have this question which I have some difficulties with:

"Given: There is a non-deterministic Turing machine that quickly recognizes language C. Question: Is C necessarily a decidable language? If C is not necessarily decidable, is C necessarily a Turing-recognizable language? Prove your answers. Context: In a non-deterministic machine: Different computation paths may exist for the same word. The length of a computation path is the number of steps the machine executes in that computation path. A non-deterministic Turing machine N accepts a word w if there is at least one computation path of N on w that ends in an accepting state (q_accept). We say that a non-deterministic machine N "quickly accepts" a word w if at least one of the shortest computation paths of N on w ends in an accepting state. For example, if the shortest computation paths of N on w are 300 steps long, then N quickly accepts w only if there is a computation path (of N on w) of 300 steps that ends in an accepting state. If all computation paths (of N on w) of 300 steps end in the rejecting state (q_reject), then N does not quickly accept w (even though N may accept w). The language that a non-deterministic machine N quickly accepts is the set of words that it quickly accepts. (This language is always a subset of the language that the machine accepts.) We have a non-deterministic machine that quickly accepts C (where C is some language). Is C necessarily Turing-recognizable? or decidable? prove your answer."

I was able to prove that C is not decidable, but I can't prove it to be RE. I would appreciate some help on this one

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you credit the source of the question? What were your attempts? $\endgroup$ Commented Aug 4, 2024 at 13:29
  • $\begingroup$ That's a question from a past exam from my university, so unfortunately I can't share the file (due to copyrights). I tried describing a TM that recognizes C, but I couldn't quite get there. Not sure how to use the non-deterministic machine that "quickly accepts" C. $\endgroup$ Commented Aug 4, 2024 at 13:52

1 Answer 1

Reset to default
3
$\begingroup$

1- In the deterministic setting, quickly acceptance and acceptance coincide. Hence, a deterministic machine $M$ quickly recognizes a language $L$ iff it recognizes $L$. As there are languages that can be recognized by a deterministic machine, yet are not decidable (such as the halting problem), it follows that $C$ is not necessarily decidable.

2- Regard whether $C$ is in $\text{RE}$: the answer is positive. The idea is as follows. Let $N$ be a nondeterministic Turing machine that quickly recognizes $C$. Note that it could be the case that $C$ is strictly included in $L(N)$. Yet, we will show nonetheless that $C$ can be recognized by a nondeterministic machine $T$ as follows. On input $x$, the machine $T$ nondeterministically simulates the run of $N$ on $x$ while counting the number of simulated steps. Let $i$ denote the number of simulated steps so far. If the simulated run is accepting, then $T$, goes over all possible runs of $N$ on $x$ whose length is at most $i-1$. If all of these runs are not final (did not halt), $T$ accepts, otherwise $T$ rejects. So essentially $T$ works as $N$ except that when it reaches an accepting state of $N$, it accepts only when there are no shorter accepting or rejecting runs. Try to prove that $T$ indeed recognizes $C$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Danielle If you find the question correct or helpful, you can thank me by accepting the answer or upvoting it :) $\endgroup$ Commented Aug 4, 2024 at 16:25
  • $\begingroup$ @Danielle, you can accept an answer by checking the 'checkbox' / 'tickbox' underneath the voting arrows, even if you are new. $\endgroup$ Commented Aug 5, 2024 at 3:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.