Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Theorie 4)
 

 
 
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.


  • 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.)
 
Definition von "berechenbar"
 
Eine Funktion heißt berechenbar, wenn es eine Turingmaschine gibt, so dass
  • zu Beginn die Argumente der Funktion auf dem Band stehen,
  • die Turingmaschine nach endlich vielen Schritten hält
  • und am Ende der Funktionswert auf dem Band steht.

 
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.
 
Seite 14/17