Abstract

A new method of coding Diophantine equations is introduced. This method allows checking that a coded sequence of natural numbers is a solution of a coded equation without decoding; defining by a purely existential formula, the code of an equation equivalent to a system of indefinitely many copies of an equation represented by its code. The new method leads to a much simpler construction of a universal Diophantine equation and to the existential arithmetization of Turing machines, register machines, and partial recursive functions