MuPAD codes which implement limit-computable functions that cannot be bounded by any computable function

الأصل · EN

For a positive integer n, let f(n) denote the smallest non-negative integer b such that for each system S xₖ=1,xᵢ+xⱼ=xₖ,xᵢ*xⱼ=xₖ: i,j,k ∈ 1,...,n with a solution in non-negative integers x₁,...,xₙ, there exists a solution of S in 0,...,bⁿ. We prove that the function f is strictly increasing and dominates all computable functions. We present an infinite loop in MuPAD which takes as input a positive integer n and returns a non-negative integer on each iteration. Let g(n,m) denote the number returned on the m-th iteration, if n is taken as input. Then, g(n,m) ≤ m-1, 0=g(n,1)<1=g(n,2) ≤ g(n,3) ≤ g(n,4) ≤... and g(n,f(n))<f(n)=g(n,f(n)+1)=g(n,f(n)+2)=g(n,f(n)+3)=.... A MuPAD code constructed on another principle contains a repeat-until loop and implements a limit-computable function ξ: N-->N that cannot be bounded by any computable function. This code takes as input a non-negative integer n, immediately returns 0, and computes a system S of polynomial equations. If the loop terminates for S, then the next instruction is executed and returns ξ(n).