A short program in MuPAD that computes in the limit a function f:N→N which eventually dominates every computable function g:N→N

08 September 2025, Version 1
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

Abstract

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)

Keywords

computable function
eventual domination
limit-computable function
non-computable function
single-fold Diophantine representation

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy [opens in a new tab] - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here [opens in a new tab] .
This site is protected by reCAPTCHA and the Google Privacy Policy [opens in a new tab] and Terms of Service [opens in a new tab] apply.