News for hackers. Stuff that matters.
Re:Every Computer System Is a State Machine by jcranmer on Friday June 05, 2020 @04:07PM (#23433331)
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.

There are no comments on this comment yet.