Eine Abbildung von endlich kodierten Eingaben (üblich endliche Zeichenketten oder natürliche Zahlen) auf Ausgaben, für die ein endliches, mechanisch ausführbares Verfahren existiert, das für jede gültige Eingabe terminiert und die korrekte Ausgabe liefert.

Prinzip

Berechenbarkeit ist die Existenz eines effektiven endlichen Verfahrens: eine einzige feste Vorschrift, die jede erlaubte Eingabe in einer endlichen Anzahl deterministischer Schritte in die Ausgabe überführt.

Demonstration

Addition natürlicher Zahlen implementiert durch eine Turing-Maschine: gegeben zwei Kodierungen, terminiert die Maschine mit der Kodierung ihrer Summe.

Fehlanwendung

Zu behaupten, eine reellwertige Funktion sei berechenbar, ohne eine Kodierung der reellen Zahlen oder ein Terminierungskriterium anzugeben, oder numerische Approximationen fälschlich als exakte Berechenbarkeit auszugeben.

Konsequenz

Ist eine Funktion berechenbar, so lässt sich ihre Auswertung mechanisieren, Entscheidbarkeitsaussagen über ihren Graphen beweisen und sie in formalen Reduktionen zwischen Entscheidungsproblemen einbetten.

Umkehrung

Eine nicht-berechenbare Funktion: kein endlicher Algorithmus existiert, der für alle zulässigen Eingaben mit korrekten Ausgaben terminiert.

Abgrenzung

Gilt nur für Funktionen mit effektiver endlicher Kodierung von Ein- und Ausgaben; schließt nicht-repräsentierte reelle Funktionen, Oracle- oder Hyperberechnungsmodelle aus und widerlegt nicht die Idee, dass probabilistische Approximationen exakte Berechenbarkeit bedeuten.

Semantische Spannung

Wird häufig mit der Entscheidbarkeit einer Menge (Mitgliedschaftsentscheidung) oder mit numerischer Approximierbarkeit verwechselt; berechenbare Funktion bedeutet explizite Ausgabeerzeugung für jede Eingabe, nicht nur Mengenmitgliedschaft oder Approximation.

Synthese

Eine berechenbare Funktion ist eine Abbildung zwischen endlich darstellbaren Objekten, für die ein einzelnes endliches mechanisches Verfahren für jede erlaubte Eingabe exakte Ausgaben liefert.