Katana VentraIP

Gödel numbering for sequences

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.[1][2]

Burris, Stanley N. (1998). . Logic for Mathematics and Computer Science. Prentice Hall. ISBN 978-0-13-285974-5.

"Supplementary Text, Arithmetic I"

Csirmaz, László; (1994). "Rekurzív függvények". Matematikai logika (postscript + gzip) (in Hungarian). Budapest: Eötvös Loránd University. Each chapter is downloadable verbatim on author's page.

Hajnal, András

Hughes, John (1989). . Computer Journal. 32 (2): 98–107. doi:10.1093/comjnl/32.2.98. Archived from the original on December 8, 2006.

"Why Functional Programming Matters"

Monk, J. Donald (1976). . Graduate Texts in Mathematics. New York • Heidelberg • Berlin: Springer-Verlag. ISBN 9780387901701.

Mathematical Logic

(1992). Gödel's Incompleteness Theorems. Oxford University Press. ISBN 978-0-19-504672-4.

Smullyan, Raymond Merrill

(2003). Gödel nemteljességi tételei (in Hungarian). Budapest: Typotex. ISBN 978-963-9326-99-6. Translation of Smullyan 1992.

Smullyan, Raymond Merrill

Burris, Stanley N. (1998). . Logic for Mathematics and Computer Science. Prentice Hall. ISBN 978-0-13-285974-5.

"Supplementary Text, Arithmetic I"