In mathematics, 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 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 functions. It is usually used to build sequential "data types" in arithmetic-based formalizations of some fundamental notions of mathematics. It is a specific case of the more general idea of Gödel numbering. For example, recursive function theory can be regarded as a formalization of the notion of an algorithm, and can be regarded as a programming language to mimic lists by encoding a sequence of natural numbers in a single natural number.
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 or one-to-one correspondence with the sequences), we can use it to encode whole "architectures" of sophisticated "machines". For example, we can encode Markov algorithms, or Turing machines 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 by using a pairing function. We expect that there is an effective way for this information retrieval 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 ⟨ a 0 , … a n − 1 ⟩ {\displaystyle \langle a_{0},\dots a_{n-1}\rangle } , there exists an appropriate natural number a, called the Gödel number of the sequence, such that for all i where 0 ≤ i ≤ n − 1 {\displaystyle 0\leq i\leq n-1} , f ( a , i ) = a i {\displaystyle f(a,i)=a_{i}} . 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, we can constructively define such a recursive function β {\displaystyle \beta } (using simple number-theoretical functions, all of which can be defined in a total recursive way) fulfilling the specifications given above. Gödel defined the β {\displaystyle \beta } function using the Chinese remainder theorem in his article written in 1931. This is a primitive recursive function. Thus, for all n and for any n-length sequence of natural numbers ⟨ a 0 , … a n − 1 ⟩ {\displaystyle \langle a_{0},\dots a_{n-1}\rangle } , there exists an appropriate natural number a, called the Gödel number of the sequence such that β ( a , i ) = a i {\displaystyle \beta (a,i)=a_{i}} .
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 of the pairing function. We need only to know its "interface": let π {\displaystyle \pi } , K, and L denote the pairing function and its two projection functions, respectively, satisfying specification:
K ( π ( x , y ) ) = x {\displaystyle K\left(\pi \left(x,y\right)\right)=x}
L ( π ( x , y ) ) = y {\displaystyle L\left(\pi \left(x,y\right)\right)=y}
Remainder for natural numbers We shall use another auxiliary function that will compute the remainder for natural numbers. Examples:
r e m ( 5 , 3 ) = 2 {\displaystyle \mathrm {rem} (5,3)=2}
r e m ( 7 , 2 ) = 1 {\displaystyle \mathrm {rem} (7,2)=1}
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, we can prove that implementing β {\displaystyle \beta } as
… excerpt ends here. Continue reading the full article.
