Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Also posted to MO,… – Gerry Myerson Jan 7 '14 at 21:05

The Diophantine equations are a programming language and you should expect that anything that can be detected automatically by a compiler has an equivalent in the structure of the Diophantine system, while any nontrivial semantic property that (by, e.g., Rice's theorem) cannot be recognized by a compiler will not have an identifiable common effect on programs, in any fixed system of Diophantine encoding.

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.

Syntactic implementations of polynomial time requirements can be done using a FOR loop or other clock mechanism independent of the other content of the program, and this would be reflected in both the structure of the system and the asymptotic relations between variables in the solution.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.