Can you prove mu-recursive functions are Diophantine without bounded universal quantifiers?

46 Views Asked by At

Most proofs I’ve come across for the unsolvability of Hilbert’s tenth problem show that every recursive function is Diophantine using the approach of mu-recursive functions, i.e. they show that the zero function, the successor function, and the projection function are Diophantine functions, and then they show that composition, primitive recursion, and minimization preserve being a Diophantine function. And they end up using the result that sets defined through bounded universal quantifiers (on top of the usual existential quantifiers) are Diophantine. But Yuri Matiyasevich, in his book Hilbert’s Tenth Problem, uses Turing machines instead of mu-recursive functions, and manages to show that every Turing machines can be simulated by a Diophantine function, in a way that does not utilize the result about bounded universal quantifiers.

So my question is, is it possible to stick with the mu-recursive function approach rather than the Turing machine approach, and still avoid using the bounded universal quantifier result? Are there any proofs that have done this?