Re:Accidentally Turing-Complete
by Dylan16807 on Friday April 24, 2020 @10:37AM
(#22968389)
A machine that has a stack and runs a series of instructions in sequence, no looping or branching, is a pushdown automaton. That's significantly weaker than Turing complete.
(A pushdown automaton can do branching if it wants, but the lack of looping / going left is critical.)
(A pushdown automaton can do branching if it wants, but the lack of looping / going left is critical.)