NDTM == DTM ?

[wij]

Is NDTM computationally equivalent to DTM?
https://en.wikipedia.org
wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
Average books say yes, but I doubt. Reason is simple. 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?

[Richard Damon]

Generally, a Non-Deterministic Turing Machine is defined to accept if
ANY of the multiple paths reaches an accept state.

One way to simulate a NDTM is to keep the history of states that you
have come from as you do a breadth first seach of states to see if you
find an accept state.

Note, a NDTM that isn't required to halt isn't a DECIDER, but just a
RECOGNIZER, and a DTM RECOGNIZER isn't required to halt either.

If you need a NDTM DECIDER, then ALL the branches DO need to reach an
explicit REJECT state for it to answer with REJECT.

It is just that DTM are more apt to be talked of as Deciders vs
Recognizers, while NDTM are more apt to just be talked about as a
Recognizer.

Thus, they can do exactly the same set of computations with the same
defined requirements, just at a different complexity level.

[Ben Bacarisse]

wij <wyni...@gmail.com> writes:

> Is NDTM computationally equivalent to DTM?
> https://en.wikipedia.org
> wiki/Nondeterministic_Turing_machine#DTM_simulation_of_NTM
> 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
stop trying.

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.

--
Ben.

[wij]

OK, that makes sense, thanks.