# Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine.

Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or polimomials-computable functions). There is subset of set of all Diophantine's set that is corresponded to $S$. Is it possible to describe this subset easier in some cases?

-
Also posted to MO, mathoverflow.net/questions/153627/… – Gerry Myerson Jan 7 '14 at 21:05

Grzegorczyk's class corresponds to a syntactic programming constraint, bounded number of FOR-NEXT loops, and this would mean a Diophantine system formed by a bounded number of encodings of the loops. Your question would then amount to "how is a FOR loop expressed in a given solution method for Hilbert's 10th problem". There are several methods, and I certainly do not remember the details , but in any approach to the problem it is something relatively modular that is visible in the construction of the equation system, such as adding several new variables $x_1, \dots x_k$ and relations between them (to write the outer wrapping of the loop) plus a relation to whichever old variables are used in the code that is iterated inside the loop.
Polynomial runtime is a semantic constraint. It would be visible in the fine structure of the asymptotics of the solutions to the Diophantine system (of the $n$ variables, at least one of them will be polynomially bounded as a function of some of the others, or whatever bound is equivalent to polynomial taking into account the explosion in size from all the encoding), but not in the structure of the system of equations.