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

Computable Economy
Computable Economy
The recent arrival of an innovation supercluster of digital business technologies (web3/ industry 4.0, etc) is driving a deep, global institutional transformation from industrial t...
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....
Development of ACERA Learning Model Based on Proof Construction Analysis
Development of ACERA Learning Model Based on Proof Construction Analysis
Proof constructing is the process of justifying a claim using the methods and concepts of proof to produce mathematical proof. Proof constructing is also an aspect of proof, and is...
(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...
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...
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 ...

Back to Top