> Is NDTM computationally equivalent to DTM?
> Average books say yes, but I doubt. Reason is simple.
That should give you pause. Unless you think there is a deliberate,
decades-long conspiracy between thousands of authors, editors,
professors and researchers to hide the truth, simple mistakes like the
one you think you've spotted are not going go unnoticed.
> The decision problems DTM compute have to terminate, while NDTM is not
> required. The 'no' answer for a NDTM is not required to compute, how
> can a DTM simulate such a case?
A NDTM rejects an instance if, and only if, all paths lead to final
reject state. I think was it bothering you is that there is no way to
tell if this will ever happen. And you are right. Since halting is
undecidable for NDTMs and DTMs alike, there is no algorithm by which a
deterministic TM, simulating a non-deterministic TM, can tell when to
But every NDTM /decider/ either accepts or rejects. So an equivalent
DTM can just keep going because it will, also, eventually accept or
reject not matter what the input is. Any NDTM decidable set it
therefore also DTM decidable.