Was bisher geschah
Wir haben gesehen, dass die Turingmaschine sehr hilfreich ist, wenn man nachweisen möchte, dass ein Problem nicht berechenbar oder nicht entscheidbar ist.
Eine Funktion heißt berechenbar, wenn es eine Turingmaschine gibt, so dass
Mehr Probleme als Lösungen
Dass nicht jede Funktion berechenbar ist, weiß man schon länger. Es gibt nämlich in der Mathematik mehr Funktionen als Berechnungsverfahren. Es war allerdings lange Zeit keine konkrete Funktion bekannt, die nicht berechenbar ist.
Im Jahre 1962 konnte eine nicht berechenbare Funktion angegeben werden und auch dabei spielte die Turingmaschine wieder eine entscheidende Rolle.