Wir haben gesehen, dass die Turingmaschine sehr hilfreich ist, wenn man nachweisen möchte, dass ein Problem nicht berechenbar oder nicht entscheidbar ist.

• Beispiele für nicht entscheidbare Probleme haben wir bereits kennengelernt.
  
  (Entscheidungsproblem, Halteproblem)
  
  
• Beispiele für nicht berechenbare Funktionen haben wir noch nicht kennengelernt.
  
  (Bei Fragen der Berechenbarkeit spricht man von Funktionen statt von Problemen.)

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.