Skip to content

Comment on Every Computer System Is a State Machineparent

Comments

A nondeterministic Turing machine is no more powerful than its deterministic Turing machine, if you define "powerful" as "can solve problems." If you instead define "powerful" as "can solve problems within a given amount of time," then there may be a distinction.

Put another way, you can simulate a nondeterministic Turing machine with a deterministic one, just as you can simulate a nondeterministic finite-state machine with a deterministic one. However, this simulation does come with increased time and space requirements.

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.