berechenbare Funktion (Informatik)

eine Funktion f : M ⟶ N, für die es einen Algorithmus gibt, der für jeden Eingabewert m ∊ M, für den die Funktion definiert ist, nach endlich vielen Schritten anhält und das Ergebnis f(m) liefert; in allen Fällen, in denen f(m) nicht definiert ist, bricht der Algorithmus nicht ab.