Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Theorie 1)
 

 
 
Warten oder Neustart?
 
Sicher kennst du das folgende Problem. Du sitzt vor deinem Bildschirm und fragst dich:


"Ist der Computer abgestürzt oder rechnet er noch?"


Vielleicht entscheidest du dich, ein Programm zu entwickeln, das diese Frage beantwortet. Du gründest also eine Firma, stellst 10 Programmierer ein und beauftragst diese damit, ein Programm zu schreiben, das Folgendes leistet:
 

 
Zu einem beliebigen Programm und einem Satz von Eingabedaten soll entschieden werden, ob dieses Programm mit diesen Daten nach endlicher Zeit stoppt oder nicht.
 
Theorie kann manchmal ganz praktisch sein.
 
Nach 6 Monaten hat noch keiner deiner Programmierer eine Lösung des Problems entwickelt. Und nun?

Am besten du schließst deine Firma wieder, denn das Problem ist in der Theoretischen Informatik wohlbekannt. Es handelt sich um das Halteproblem und das ist nicht lösbar:
 
Halteproblem
 
Man kann beweisen, dass es kein Programm gibt, welches obige Frage beantwortet.
 
Seite 11/17