15 views

Skip to first unread message

Aug 14, 2022, 2:07:46 PMAug 14

to

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?

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?

Aug 14, 2022, 2:28:16 PMAug 14

to

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.

Aug 14, 2022, 3:07:17 PMAug 14

to

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

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?

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.

Aug 15, 2022, 6:00:00 AMAug 15

to

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu