Not true. At least not a finite state machine, which is what people usually mean by “state machine”. Most problems aren’t modelable as a state machine because they need contextual memory.
But a state machine + stack, now we’re talking. That can do almost everything. State machine + “infinite” tape – yessss now we can solve everything.
Not true. At least not a finite state machine, which is what people usually mean by “state machine”. Most problems aren’t modelable as a state machine because they need contextual memory.
But a state machine + stack, now we’re talking. That can do almost everything. State machine + “infinite” tape – yessss now we can solve everything.