News for hackers. Stuff that matters.

A comment on Accidentally Turing-Complete. Parent comment

Re:Accidentally Turing-Complete by bugmen0t on Friday April 24, 2020 @10:17AM (#22968177)
Pickle is a stack machine (https://en.wikipedia.org/wiki/Stack_machine). It is Turing complete. See source code and documentation at https://github.com/python/cpython/blob/master/Lib/pickle.py#... https://github.com/python/cpython/blob/master/Lib/pickletool...

N.B: "Turing complete" really means a lot less than you seem to believe.

[ Parent | on HN ]
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.)

[ Parent | on HN ]