The Davis-Putnam-Robinson theorem showed that every partially computable $m$-ary function f(a1, ..., am) = c on the natural numbers can be specified by means of an exponential Diophantine formula involving, along with parameters a1, ... am, 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 a1, ... am have been fixed, is solved by at most one tuple < v0, ..., vk > 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
Alberto Casagrande;Francesco Fabris;Eugenio Omodeo
2021-01-01
Abstract
The Davis-Putnam-Robinson theorem showed that every partially computable $m$-ary function f(a1, ..., am) = c on the natural numbers can be specified by means of an exponential Diophantine formula involving, along with parameters a1, ... am, 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 a1, ... am have been fixed, is solved by at most one tuple < v0, ..., vk > 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.File | Dimensione | Formato | |
---|---|---|---|
2044-Article Text-6438-2-10-20210705.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Documento in Versione Editoriale
Licenza:
Creative commons
Dimensione
251.51 kB
Formato
Adobe PDF
|
251.51 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.