The Davis-Putnam-Robinson theorem showed that every partially computable m-ary function f (a(1), ..., a(m)) = c on the natural numbers can be specified by means of an exponential Diophantine formula involving, along with parameters a(1), ..., a(m), c, some number k of existentially quantified variables. Yuri Matiyasevich improved this theorem in two ways: on the one hand, he proved that the same goal can be achieved with no recourse to exponentiation and, thereby, he provided a negative answer to Hilbert's 10th problem; on the other hand, he showed how to construct an exponential Diophantine equation specifying f which, once a(1,) ..., a(m) have been fixed, is solved by at most one tuple v(0), ..., v(k) i of values for the remaining variables. This latter property is called single-foldness. Whether there exists a single-(or, at worst, finite-) fold polynomial Diophantine representation of any partially computable function on the natural numbers is as yet an open problem. This work surveys relevant results on this subject and tries to draw a route towards a hoped-for positive answer to the finite-fold-ness issue.

### THE QUEST FOR DIOPHANTINE FINITE-FOLD-NESS

#### Abstract

The Davis-Putnam-Robinson theorem showed that every partially computable m-ary function f (a(1), ..., a(m)) = c on the natural numbers can be specified by means of an exponential Diophantine formula involving, along with parameters a(1), ..., a(m), c, some number k of existentially quantified variables. Yuri Matiyasevich improved this theorem in two ways: on the one hand, he proved that the same goal can be achieved with no recourse to exponentiation and, thereby, he provided a negative answer to Hilbert's 10th problem; on the other hand, he showed how to construct an exponential Diophantine equation specifying f which, once a(1,) ..., a(m) have been fixed, is solved by at most one tuple v(0), ..., v(k) i of values for the remaining variables. This latter property is called single-foldness. Whether there exists a single-(or, at worst, finite-) fold polynomial Diophantine representation of any partially computable function on the natural numbers is as yet an open problem. This work surveys relevant results on this subject and tries to draw a route towards a hoped-for positive answer to the finite-fold-ness issue.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
File in questo prodotto:
File
2044-Article Text-6438-2-10-20210705.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 251.51 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11390/1262164`