Gödel numbering for sequences

In mathematics, a Gödel numbering for sequences provides us an effective way to represent each finite sequence of natural numbers as a single natural number. Of course, the embedding is surely possible set theoretically, but 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 the realm of 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 if we regard it as a programming language, we can mimic lists by encoding a sequence of natural numbers in a single natural number. To achieve this, we can use various number theoretic ideas; using the fundamental theorem of arithmetic is a straightforward way, but there are also more economic approaches, such as using the pairing function combined with the Chinese remainder theorem in a sophisticated way.

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.

...
Wikipedia