[FOM] Canonical Turing-complete set

[Joe Shipman]

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?

— JS


Sent from my iPhone