Merke

Mit keinem heutigen Rechner und keiner heutigen Programmiersprachen können Funktionen berechnet werden, die nicht auch mit einer Turingmaschine berechnet werden können.

Die Turingmaschine ist ein allgemeines Modell für die Berechenbarkeit.

Entscheidbarkeit

Ein Problem P ist entscheidbar, wenn es einen Algorithmus gibt, der für P mit Ja oder Nein beantwortet werden kann.

Unentdcheidbare Probleme

Z.B. Kommt eine bestimmte Ziffernfolge im Nachkommsteil von Pi vor?