2A00:6020:4903:5300:DD7B:F20D:54EE:9F74 am 9. Februar 2022 um 07:33 Uhr

2022-02-09T07:33:23Z

Neue Seite

Eine '''Wortfunktion''' ist eine [[Funktion (Mathematik)|Funktion]], die von einer k-stelligen [[Wortmenge]] in eine Wortmenge führt. Statt Wortmenge verwendet man auch den Begriff „[[formale Sprache]]“.

[[Turingmaschine]]n berechnen Wortfunktionen.

Der Begriff wird hauptsächlich in der [[Theoretische Informatik|theoretischen Informatik]] in der Theorie der [[Berechenbarkeit]] verwendet und dient der Abgrenzung zu Funktionen über anderen Mengen, insbesondere [[Zahlenfunktion]]en.

== Formale Definition ==
Eine Wortfunktion ist eine möglicherweise [[partielle Funktion]] <math>f :\subseteq \left(\Sigma^*\right)^k \to \Sigma^*</math>.

Dabei steht <math>\left(\Sigma^*\right)^k</math> für das k-fache [[kartesisches Produkt|kartesische Produkt]] <math>\times_{i=1}^k \Sigma^*</math>, also die Menge der [[Tupel]] der Länge k mit endlichen Worten über dem [[Alphabet]] <math>\Sigma</math> als Komponenten.

== Bedeutung ==
In der Theorie der Berechenbarkeit kann man zeigen, dass sich Funktionen über beliebigen Wortmengen durch die [[Standardnummerierung]] <math>\nu:\Sigma^*\to\mathbb{N}</math> von <math>\Sigma^*</math> auf Zahlenfunktionen abbilden lassen.

:<math>\begin{matrix}
f_\Sigma: & \left(\Sigma^*\right)^k & \longrightarrow & \Sigma^* \\
& \vec{\nu} \downarrow & & \downarrow \nu \\
f_\mathbb{N}: & \mathbb{N}^k & \longrightarrow & \mathbb{N} \end{matrix}</math>

Damit kann man weiter zeigen, dass die Menge der berechenbaren Wortfunktionen genau der Menge der berechenbaren Zahlenfunktionen entspricht.

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Berechenbarkeitstheorie]]

Wortfunktion - Versionsgeschichte

2A00:6020:4903:5300:DD7B:F20D:54EE:9F74 am 9. Februar 2022 um 07:33 Uhr