Abstract

We present a new constructive proof of the following theorem: there exists a limit-computable function β_1:N→N which eventually dominates every computable function δ_1:N→N. We prove: (1) there exists a limit-computable function f:N→N of unknown computability which eventually dominates every function δ:N→N with a single-fold Diophantine representation, (2) statement (1) significantly strengthens a non-trivial mathematical theorem, (3) Martin Davis' conjecture on single-fold Diophantine representations disproves (1). We present both constructive and non-constructive proof of (1).