3 ms·

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 r

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... 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 https://github.com/moreati/pickle-fuzz

bugmen0t 6y ago
Pickle is a stack machine (https://en.wikipedia.org/wiki/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#L107and https://github.com/python/cpython/blob/master/Lib/pickle.py#... https://github.com/python/cpython/blob/master/Lib/pickletools.py#L38 https://github.com/python/cpython/blob/master/Lib/pickletool... N.B: "Turing complete" really means a lot less than you seem to believe.
- Dylan16807 6y ago
  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.)