3
$\begingroup$

From a well-known work(s) by Putnam, Davis, Robinson and Matiyasevich, we know that every partially recursive function is diophantine. Now it seems a natural question to ask: can we say something nontrivial about classes of diophantine functions that corresponds to some weaker classes of functions from computability theory (e.g. Kalmar elementary or primitive resursive functions)? I have not seen any work on this topic. Have I missed something? Or maybe there is no "naturally occuring" characterization of weaker classes of functions in term of diophantine equations?

I know this question may sound vague, but surely one can think of some more specific problems. We know, for example, that problem of existence of solutions for an arbitrary diophantine equation can be reduced to similar problem for some diophantine equation with 13 arguments (Y. Matiyasevich & J. Robinson 1975). Let's take only those diophantine equations that define primitively recursive functions (or Kalmar elementary). Clearly, there is the smallest $n\leq 13$ such that problem of existence of solutions for those equations can be reduced to existence of solutions for some $n$-ary equations. Is $n<13$ or $n=13$ ? There are probably some more interesting questions to ask.

So: do you know any research concerning such weaker classes of diophantine functions?

Best regards.

$\endgroup$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.