I currently have a problem with the following question:

Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$. Construct an NTM (non-deterministic Turing machine) that decides $L$.

My idea was to simulate every possible input of length $\le|w|^3$ on a given TM $M$ by using a separate band in my NTM for every single input word. If there is one band where $M$ halts, then the NTM accepts.

Is this the right way to go about it? My problem is that I don't see why I would need a NTM to decide $L$. A standard TM would be able to do the same thing.

  • $\begingroup$ "simulate every possible input"... Are you sure you can do this in finite time? For every possible input? Remember deciders need to halt to reject too! $\endgroup$ – dkaeae Jan 7 at 15:10
  • $\begingroup$ Also, are you sure you mean "at least $|w|^3$ steps" and not "at most $|w|^3$ steps"? $\endgroup$ – dkaeae Jan 7 at 15:13
  • $\begingroup$ sorry you are right, I meant at most |w|^3 steps. If it doesn't halt until then, I know that it is the wrong input. $\endgroup$ – freak14 Jan 7 at 15:38
  • $\begingroup$ maybe it helps to know that I use a NTM to show that L ist semi-decidable $\endgroup$ – freak14 Jan 7 at 15:47
  • $\begingroup$ Wait... Are you supposed to prove $L$ is decidable or semi-decidable? I do not think the former is correct... $\endgroup$ – dkaeae Jan 8 at 12:29

$L$ is semi-decidable (or, synonymously, recursively enumerable). This can be proven (arguably) more easily by using an NTM which non-deterministically picks an input $w \in \{ 0, 1 \}^\ast$, simulates $M$ on it for at most $|w|^3$ steps, and accepts if and only if $M$ does. The NTM accepts exactly the language $L$ because, if there is no accepting branch of the NTM, then there is also no input $w$ for which $M$ halts in at most $|w|^3$ steps. For a properly written proof, it should also be said the semi-decidability of $L$ follows from the equivalence of DTM and NTM acceptors (remember (semi-)decidability is defined in terms of DTMs, not NTMs!).

Because of the equivalence of DTM and NTM acceptors, the above reasoning indirectly gives you a DTM which accepts $L$. The explicit construction could be picking an enumeration of inputs (e.g., lexicographical order), simulating $M$ on each input $w$ for at most $|w|^3$ steps, and accepting if and only if $M$ does. (Having to argue about the enumeration of inputs might be perceived as "hard" by some, hence why proving with an NTM could be considered "easier".)

A warning, however: $L$ is not decidable. This is because its complement is $\{ \langle M \rangle \mid \forall w: \text{$M$ does not halt for $w$ in at most $|w|^3$ steps} \}$ and, thus, a variant of the complement of the halting problem, which is notorious for not being semi-decidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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