In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a Gödel numbering for sequences provides an effective way to represent each finite sequence of natural numbers as a single natural number. While a set theoretical
embedding
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group (mathematics), group that is a subgroup.
When some object X is said to be embedded in another object Y ...
is surely possible, the emphasis is on the effectiveness of the functions manipulating such representations of sequences: the operations on sequences (accessing individual members, concatenation) can be "implemented" using
total recursive functions, and in fact by
primitive recursive function
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...
s.
It is usually used to build sequential “
data type
In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these ...
s” in arithmetic-based formalizations of some fundamental notions of mathematics. It is a specific case of the more general idea of
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. Kurt Gödel developed the concept for the proof of his incom ...
. For example,
recursive function theory can be regarded as a formalization of the notion of an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
, and can be regarded as a
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
to mimic
list
A list is a Set (mathematics), set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of t ...
s by encoding a sequence of natural numbers in a single natural number.
[ Monk 1976: 56–58][ Csirmaz 1994: 99–100 (se]
online
Gödel numbering
Besides using Gödel numbering to encode unique sequences of symbols into unique natural numbers (i.e. place numbers into
mutually exclusive
In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
or
one-to-one correspondence
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...
with the sequences), we can use it to encode whole “architectures” of sophisticated “machines”. For example, we can encode
Markov algorithm
In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a gen ...
s,
[ Monk 1976: 72–74] or
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s
[ Monk 1976: 52–55] into natural numbers and thereby prove that the expressive power of recursive function theory is no less than that of the former machine-like formalizations of algorithms.
Accessing members
Any such representation of sequences should contain all the information as in the original sequence—most importantly, each individual member must be retrievable. However, the length does not have to match directly; even if we want to handle sequences of different length, we can store length data as a surplus member,
or as the other member of an
ordered pair
In mathematics, an ordered pair, denoted (''a'', ''b''), is a pair of objects in which their order is significant. The ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a''), unless ''a'' = ''b''. In contrast, the '' unord ...
by using a
pairing function
In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number.
Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural ...
.
We expect that there is an effective way for this
information retrieval
Information retrieval (IR) in computing and information science is the task of identifying and retrieving information system resources that are relevant to an Information needs, information need. The information need can be specified in the form ...
process in form of an appropriate total recursive function. We want to find a totally recursive function ''f'' with the property that
for all ''n'' and for any ''n''-length sequence of natural numbers
, there exists an appropriate natural number ''a'', called the Gödel number of the sequence, such that for all ''i'' where
,
.
There are effective functions which can retrieve each member of the original sequence from a Gödel number of the sequence. Moreover, we can define some of them in a
constructive way, so we can go well beyond mere
proofs of existence.
Gödel's β-function lemma
By an ingenious use of the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, we can constructively define such a recursive function
(using simple number-theoretical functions, all of which can be defined in a total recursive way) fulfilling the
specification
A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard.
There are different types of technical or engineering specificati ...
s given above. Gödel defined the
function using the Chinese remainder theorem in his article written in 1931. This is a
primitive recursive function
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...
.
Thus, for all ''n'' and for any ''n''-length sequence of natural numbers
, there exists an appropriate natural number ''a'', called the Gödel number of the sequence such that
.
[ Monk 1976: 58 (= Thm 3.46)]
Using a pairing function
Our specific solution will depend on a pairing function—there are several ways to implement the pairing function, so one method must be selected. Now, we can
abstract from the details of the
implementation
Implementation is the realization of an application, execution of a plan, idea, scientific modelling, model, design, specification, Standardization, standard, algorithm, policy, or the Management, administration or management of a process or Goal ...
of the pairing function. We need only to know its “
interface”: let
, ''K'', and ''L'' denote the pairing function and its two
projection
Projection or projections may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphics, and carto ...
functions, respectively, satisfying
specification
A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard.
There are different types of technical or engineering specificati ...
:
:
:
Remainder for natural numbers
We shall use another auxiliary function that will compute the
remainder for natural numbers. Examples:
*
*
It can be proven that this function can be implemented as a recursive function.
Using the Chinese remainder theorem
= Implementation of the β function
=
Using the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, we can prove that implementing
as
:
will work, according to the specification we expect
to satisfy. We can use a more concise form by an
abuse of notation
In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors an ...
(constituting a sort of
pattern matching
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...
):
:
Let us achieve even more readability by more
modularity
Modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a system into varying ...
and
reuse
Reuse is the action or practice of using an item, whether for its original purpose (conventional reuse) or to fulfill a different function (creative reuse or repurposing). It should be distinguished from recycling, which is the breaking down of ...
(as these notions are used in computer science
[ Hughes 1989 (se]
online
)): by defining