The quest for Diophantine finite-fold-ness

Abstract

The Davis-Putnam-Robinson theorem showed that every partially computable $m$-ary function f(a₁, ..., a_m) = c on the natural numbers can be specified by means of an exponential Diophantine formula involving, along with parameters a₁, ... 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₁, ... a_m have been fixed, is solved by at most one tuple < v₀, ..., v_k > 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.