Word function

A word function is a function that leads from a k-place word set to a word set. The term formal language is also used instead of a set of words .

Turing machines calculate word functions.

The term is mainly used in theoretical computer science in the theory of computability and serves to differentiate it from functions over other sets, especially number functions .

Formal definition

A word function is a possibly partial function . ${\displaystyle f:\subseteq \left(\Sigma ^{*}\right)^{k}\to \Sigma ^{*}}$

Here stands for the k-fold Cartesian product , i.e. the set of tuples of length k with finite words over the alphabet as components. ${\displaystyle \left(\Sigma ^{*}\right)^{k}}$ ${\displaystyle \times _{i=1}^{k}\Sigma ^{*}}$ ${\displaystyle \Sigma }$

meaning

In the theory of computability, it can be shown that functions can be mapped over any set of words through the standard numbering of to number functions. ${\displaystyle \nu :\Sigma ^{*}\to \mathbb {N} }$ ${\displaystyle \Sigma ^{*}}$

${\displaystyle {\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}}}$

With this one can further show that the set of calculable word functions corresponds exactly to the set of calculable number functions.