I'm still not sure if Python Pickles, without the GLOBAL opcode to call into Python, are Turing complete.
Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great.
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.)
Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great.
My research/tinkering so far is https://github.com/moreati/pickle-fuzz