Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation

摘要

We define functions f_1, f_2, g_1, g_2: N {0} → N {0} and prove that they do not have any finite-fold Diophantine representation. We conjecture that if a system S (≤) {x_i + x_j = x_k. x_i · x_j = x_k: i, j , k (≤) {1,...,n}} has only finitely many solutions in positive integers x_1,...,x_n, then each such solution (x_1,...,x_n) satisfies x_1,..., x_n (≤) 2~(2~(n-1)). Assuming the conjecture, we prove: (1) the functions f_1, f_2, g_1 g_2 are computable, (2) there is an algorithm which takes as input a Diophantine equation, returns an integer, and this integer is greater than the heights of integer (non-negative integer, positive integer, rational) solutions if the solution set is finite, (3) a finite-fold Diophantine representation of the function N (≥) n→2~n (≥) N does not exist, (4) if a set M (∈) N is recursively enumerable but not recursive, then a finite-fold Diophantine representation of M does not exist.