Notation (Berechenbarkeitstheorie)

Eine Notation einer Menge ${\displaystyle M}$, im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion ${\displaystyle \nu :\subseteq \Sigma ^{*}\to M}$.^[1]

Notationen und die verwandten Nummerierungen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register- und Turingmaschinen.

1. ↑ Klaus Weihrauch: Computable Analysis. 2000, S. 33, doi:10.1007/978-3-642-56999-9.