4 ms·
> >"You need 2 stacks for Turing completeness." > I am not completely sure about that assertion... What GP means is that a finite state machine is not Turing-
by deredede 2y ago
> >"You need 2 stacks for Turing completeness."
> I am not completely sure about that assertion...
What GP means is that a finite state machine is not Turing-complete, and neither is a finite state machine with a single stack (pushdown automaton / stack automation).
- klyrs 2y agoPiet is another near-exception to this -- the language only has a single "stack" but the "stack" is equipped with a 'roll' operation that cannot be implemented with a proper stack and O(1) memory.