Mathematical results related to the heuristic Principle of Computational Equivalence

[José Manuel Rodríguez Caballero]

Dear FOM members,
  The Principle of Computational Equivalence [1, 2], due to S. Wolfram, is
the heuristic statement that almost all processes (involving classical
computations) that are not obviously simple are of equivalent
sophistication. This principle has been recognized as relevant for biology
by Prof. Robert Sapolsky [3] and there may be even a quantum version of it
if J. E. Andersen's conjecture is proved [4].

  One of the tasks of mathematicians is to find conditions for which a
heuristic principle is valid and counterexamples outside this domain. So, I
would like to ask for references concerning mathematical results related to
this principle, which may be known under a different name. I guess that the
main challenge is to find precise conditions for expressing the intuitive
notion of not obviously a simple computational process.

Sincerely yours,
Jose M.

References:

[1] Wolfram, S. "The Principle of Computational Equivalence." Ch. 12 in A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 5-6 and 715-846,
2002.
URL =
https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence/

[2] Wolfram, S., Interview about the Principle of Computational Equivalence.
URL =
https://www.inc.com/allison-fass/stephen-wolfram-principle-of-computational-equivalence.html

[3] Robert Sapolsky, Lecture 22. Emergence and Complexity.
URL = https://youtu.be/o_ZuWbX-CyE

[4] J. E. Andersen, Folding of proteins and RNA using the quantum topology
of moduli spaces (the conjecture is in the last slide)
URL =
https://cityu-ias-www-upload.s3.amazonaws.com/eventpowerpoint/src/07-2%20-%20Prof.%20J%C3%B8rgen%20ANDERSEN_6bc1bc1d-a19d-47c6-ab55-2a01d99b11d3.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200507/56fa68cf/attachment.html>