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.

E.g. recursive function theory can be regarded as a formalization of notion “algorithm”, and if we regard it as a programming language, we can mimic arrays, 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, e.g. using pairing function combined with Chinese remainder theorem in a sophisticated way.

Read more about Gödel Numbering For Sequences:  Gödel Numbering, Accessing Members

Other articles related to "sequences":

Gödel Numbering For Sequences - Accessing Members - Access of Length
... If we use the above scheme for encoding sequences only in contexts where the length of the sequences is fixed, then no problem arises ... But sometimes we need dynamically stretching sequences, or we need to deal with sequences whose length cannot be typed in a static way ... In other words, we may encode sequences in an analogous way as we use lists in programming ...

Famous quotes containing the word numbering:

    The task he undertakes
    Is numbering sands and drinking oceans dry.
    William Shakespeare (1564–1616)