Eine Funktion heißt berechenbar, wenn es einen Algorithmus bzw. eine Turingmaschine gibt, die für jede Eingabe den Funktionswert berechnet und anhält.