Number function

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

A number function is a function that maps tuples of natural numbers to natural numbers.

The term is mainly used in theoretical computer science in computability theory and serves to distinguish it from functions over other sets, especially word functions . To prove the calculability of a number function, mathematical models such as the register machine , the while calculability or the μ-recursion are used .

Formal definition

A number function is a possibly partial function . ${\displaystyle f:\mathbb {N} ^{k}\to _{p}\mathbb {N} }$

Here stands for the k-fold Cartesian product , i.e. the set of tuples of length k with natural numbers as components. ${\displaystyle \mathbb {N} ^{k}}$ ${\displaystyle \prod _{i=1}^{k}\mathbb {N} }$

meaning

In the theory of calculability, one can show that functions over any set can be mapped to number functions using suitable numbering . The Cantor pairing function shows that it is sufficient to limit the theory of computability to the set of single-digit number functions . ${\displaystyle \mathbb {N} \to _{p}\mathbb {N} }$