imported>Mef.ellingen am 24. August 2019 um 23:02 Uhr

2019-08-24T23:02:57Z

Neue Seite

{{Quellen}}
Eine '''Zahlenfunktion''' ist eine [[Funktion (Mathematik)|Funktion]], die [[Tupel]] von [[natürliche Zahl|natürlichen Zahlen]] auf natürliche Zahlen abbildet.

Der Begriff wird hauptsächlich in der [[theoretische Informatik|theoretischen Informatik]] in der [[Berechenbarkeitstheorie]] verwendet und dient der Abgrenzung zu Funktionen über anderen Mengen, insbesondere [[Wortfunktion]]en. Zum Beweis der Berechenbarkeit einer
Zahlenfunktion dienen mathematische Modelle wie die [[Registermaschine]], die [[While-Berechenbarkeit]] oder die
[[μ-Rekursion]].

== Formale Definition ==

Eine Zahlenfunktion ist eine möglicherweise [[partielle Funktion]] <math>f:\mathbb{N}^k \to_p \mathbb{N}</math>.

Dabei steht <math>\mathbb{N}^k</math> für das k-fache [[kartesisches Produkt|kartesische Produkt]] <math>\prod_{i=1}^k \mathbb{N} </math>, also die Menge der [[Tupel]] der Länge k mit natürlichen Zahlen als Komponenten.

== Bedeutung ==

In der Theorie der Berechenbarkeit kann man zeigen, dass sich Funktionen über beliebige Mengen durch eine geeignete [[Nummerierung (Informatik)|Nummerierung]] auf Zahlenfunktionen abbilden lassen. Über die [[Cantorsche Paarungsfunktion]] zeigt man weiter, dass es ausreicht, sich in der Theorie der Berechenbarkeit auf die Menge der [[Stelligkeit|einstelligen]] Zahlenfunktionen <math>\mathbb N \to_p \mathbb N</math> zu beschränken.

[[Kategorie:Theoretische Informatik|Zahlenfunktion]]

Zahlenfunktion - Versionsgeschichte

imported>Mef.ellingen am 24. August 2019 um 23:02 Uhr