News for hackers. Stuff that matters.
Re:Every Computer System Is a State Machine by frabert on Friday June 05, 2020 @02:02PM (#23431684)
Do not confuse nondeterministic Turing machines with nondeterministic (finite) state machines/automata. The latter are proven to be equivalent to their deterministic counterparts, the former are not.
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.