[FOM] Canonical Turing-complete set
joeshipman at aol.com
Sat Mar 17 17:18:23 EDT 2018
What is the most “natural” or “canonical” definition of a Turing-complete set of natural numbers, one which is as independent of “coding” details as possible?
A natural enumeration of Diophantine equations of degree 4 would work. Perhaps Martin Davis knows of some Turing-complete set with a relatively natural enumeration.
If we are willing to move to functions instead of sets it is easier: f(n) = the number of polynomials in <=n variables of degree <=n with all coefficients of absolute value <=n that have integer solutions would work. And we can probably use the range of that function as a canonical Turing complete set of natural numbers.
Can anyone improve on this?
Sent from my iPhone
More information about the FOM