Computation theory: decidability and Turing-recognition

Question

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

Answer 1

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$.