Wir haben in "Berechenbarkeitstheorie" Berechenbarkeit wie folgt definiert:
Eine Funktion [mm] $f:\IN\to\IN$ [/mm] heißt (Turing-)berechenbar, falls eine Turningmaschine $T$ existiert, die bei Eingabe von [mm] $n\in \IN$ [/mm] terminiert und nach Terminierung von $T$ $f(n)$ auf dem Band steht
