[FOM] Canonical Turing-complete set

Joe Shipman 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?

— JS

Sent from my iPhone

More information about the FOM mailing list