Rédiger un PREreview

It is known that there exists a limit-computable function f:N→N which is not computable. Every known proof of this fact does not lead to the existence of a short computer program that computes f in the limit. For n∈N, let E_n={1=x_k, x_i+x_j=x_k, x_i·x_j=x_k: i,j,k∈{0,...,n}}. For n∈N, f(n) denotes the smallest b∈N such that if a system of equations S⊆E_n has a solution in N^{n+1}, then S has a solution in {0,...,b}^{n+1}. The author proved earlier that the function f:N→N is computable in the limit and eventually dominates every computable function g:N→N. We present a short program in MuPAD which for n∈N prints the sequence {f_i(n)}_{i=0}^∞ of non-negative integers converging to f(n). For n∈N, β(n) denotes the smallest b∈N such that if a system of equations S⊆E_n has a unique solution in N^{n+1}, then this solution belongs to {0,...,b}^{n+1}. The author proved earlier that the function β:N→N is computable in the limit and eventually dominates every function δ:N→N with a single-fold Diophantine representation. The computability of β is unknown. We present a short program in MuPAD which for n∈N prints the sequence {β_i(n)}_{i=0}^\infty of non-negative integers converging to β(n).