# How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?

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.

• "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! Jan 7 '19 at 15:10
• Also, are you sure you mean "at least $|w|^3$ steps" and not "at most $|w|^3$ steps"? Jan 7 '19 at 15:13
• 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. Jan 7 '19 at 15:38
• maybe it helps to know that I use a NTM to show that L ist semi-decidable Jan 7 '19 at 15:47
• Wait... Are you supposed to prove $L$ is decidable or semi-decidable? I do not think the former is correct... Jan 8 '19 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.