[FOM] Canonical Turing-complete set

[Harvey Friedman]

JOE SHIPMAN WROTE
https://cs.nyu.edu/pipermail/fom/2018-March/020883.html

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?

*******

See

65. (with T. Erdelyi), The Number of Certain Integral Polynomials and
Nonrecursive Sets of Integers, Part I, Transactions of the AMS, 357,
(2005), 999-1011.

66. The Number of Certain Integral Polynomials and Nonrecursive Sets
of Integers, Part II, Transactions of the AMS, 357 (2005), 1013-1023.

Harvey Friedman