Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Theorie 2)
 

 
 

 
Eine ähnlich prinzipielle Frage stellte der Mathematiker David Hilbert im Jahre 1900 auf einem Kongress in Paris.
 
Das Hilbertsche Entscheidungsproblem
 
Gibt es ein Verfahren, das für jede ausreichend formalisierte Aussage der Mathematik entscheidet, ob diese wahr oder falsch ist?
 

 
Eine positive Lösung des Problems hätte zur Folge gehabt, dass Computer mathematische Aussagen erzeugen und auch gleich noch deren Wahrheit oder Falschheit beweisen könnten.
 
Erst 1936 wurde das Problem gelöst







Nicht-Existenz ist oft schwer zu beweisen
 
Erst im Jahr 1936 konnten sowohl Alonzo Church als auch Alan Turing beweisen, dass obiges Entscheidungsproblem nicht lösbar ist.


Warum hat es 36 Jahre gedauert, bis das Problem gelöst wurde?
  • Wenn man beweisen will, dass ein Verfahren zur Lösung eines Problems existiert, dann ist es das Einfachste, man gibt das Verfahren an.
  • Wenn man aber nachweisen möchte, dass kein Verfahren zur Lösung eines Problems existiert, dann muss man beschreiben, was ein Verfahren überhaupt ist! D.h. man muss klären, aus welchen elementaren Anweisungen ein Verfahren aufgebaut ist und wie sich ein Mensch oder eine Maschine verhalten, wenn sie diese Anweisungen ausführen.

Genau diese Überlegungen haben Alan Turing 1936 zu der Idee der Turingmaschine geführt.
 
Seite 12/17