Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

The most effective proof that there exists a non-computable function from N to N

View through CrossRef
For n∈N, f(n) denotes the smallest b∈N such that if a system of equations S⊆{1=x_k, x_i+x_j=x_k, x_i·x_j=x_k: i,j,k∈{0,...,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 simple code 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, h(n) denotes the smallest b∈N such that if a system of equations S⊆{x_i+1=x_k, x_i·x_j=x_k: i,j,k∈{0,...,n}} has a solution in N^{n+1}, then S has a solution in {0,...,b}^{n+1}. The function h:N→N is computable in the limit and eventually dominates every computable function g:N→N. A bit shorter code in MuPAD computes h in the limit. It establishes the most effective proof that there exists a non-computable function from N to N.
Title: The most effective proof that there exists a non-computable function from N to N
Description:
For n∈N, f(n) denotes the smallest b∈N such that if a system of equations S⊆{1=x_k, x_i+x_j=x_k, x_i·x_j=x_k: i,j,k∈{0,.
,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 simple code 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, h(n) denotes the smallest b∈N such that if a system of equations S⊆{x_i+1=x_k, x_i·x_j=x_k: i,j,k∈{0,.
,n}} has a solution in N^{n+1}, then S has a solution in {0,.
,b}^{n+1}.
The function h:N→N is computable in the limit and eventually dominates every computable function g:N→N.
A bit shorter code in MuPAD computes h in the limit.
It establishes the most effective proof that there exists a non-computable function from N to N.

Related Results

On free proof and regulated proof
On free proof and regulated proof
Free proof and regulated proof are two basic modes of judicial proof. The system of ‘legal proof’ established in France in the 16th century is a classical model of regulated proof....
Guiding principles for technical infrastructure to support computable biomedical knowledge
Guiding principles for technical infrastructure to support computable biomedical knowledge
AbstractOver the past 4 years, the authors have participated as members of the Mobilizing Computable Biomedical Knowledge Technical Infrastructure working group and focused on conc...
(Invited) A 1-mG MEMS Sensor
(Invited) A 1-mG MEMS Sensor
MEMS (microelectromechanical systems) technology has contributed substantially to the miniaturization of inertial sensors, such as accelerometers and gyroscopes [1]. Nowadays, MEMS...
The Burden of Proof on Gang-related Property: Defunctionalization and Regulation
The Burden of Proof on Gang-related Property: Defunctionalization and Regulation
Anti-Organized Crime Law establishes the proof system of gang-related property. However, due to the abstraction of the proof system and the disagreement of the distribution of the ...
Two Undecidable Decision Problems on an Ordered Pair of Non-Negative Integers
Two Undecidable Decision Problems on an Ordered Pair of Non-Negative Integers
For \(n \in {\mathbb{N}}\), let \(E_{n} = {\{{{1 = x_{k}},{{{x_{i} + x_{j}} = x_{k}},{{x_{i} \cdot x_{j}} = x_{k}}}}:{{i,j,k} \in {\{ 0,\ldots,n\}}}\}}\). For \(n \in {\mathbb{N}}\...
A Characterization of Strongly Computable Finite Factorization Domains
A Characterization of Strongly Computable Finite Factorization Domains
Abstract In [4], Mileti and others study the prime and irreducible elements of strong finite factoriza-tion domains. The authors define the class of Strongly Computable Str...
Can a computer proof be elegant?
Can a computer proof be elegant?
In computer science, proofs about computer algorithms are par for the course. Proofs by computer algorithms, on the other hand, are not so readily accepted....

Back to Top