Mathematical results related to the heuristic Principle of Computational Equivalence

[Mitchell Spector]

Is any example known of a natural recursively enumerable set of Turing degree intermediate between 0 
and 0'?  Or is there a definition of "natural" under which one can prove that there is no such set?

Lachlan proved that any construction of such a set can't be relativizable in a uniform way. 
Reference: Lachlan, A. H. “Uniform Enumeration Operations.” The Journal of Symbolic Logic, vol. 40, 
no. 3, 1975, pp. 401–409. JSTOR, www.jstor.org/stable/2272164. Accessed 7 May 2020.


Mitchell Spector



José Manuel Rodríguez Caballero wrote:
> 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
> 
>