The quest for Diophantine finite-fold-ness
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.
Copyright (c) 2021 D. Cantone, A. Casagrande, F. Fabris, E. Omodeo
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors retain all rights to the original work without any restrictions.
License for Published Contents
"Le Matematiche" published articlesa are distribuited with Creative Commons Attribution 4.0 International. You are free to copy, distribute and transmit the work, and to adapt the work. You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
License for Metadata
"Le Matematiche" published articles metadata are dedicated to the public domain by waiving all publisher's rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
No Fee Charging
No fee is required to complete the submission/review/publishing process of authors paper.