Halteproblem

Das Halteproblem taucht bei jeder Turing-Maschine auf. Die Turingmaschinen sind getunt, was dazu führt, dass sie jede beliebige Strecke zurücklegen können. Allerdings verzettelt sich ihr Navigationssystem von Zeit zu Zeit und sie fahren dann Schleifen. Manchmal scheint es so, dass eine Turing-Maschine aus einer Schleife gar nicht wieder herauskommt. Das tritt besonders oft beim Nürburgring auf. Kann eine Turing-Maschine halten? Man weiß es nicht genau.

Für den Beweis, dass jeder Turing-Maschine mal der Sprit ausgeht, wurde ein hoher Preis ausgesetzt.

Das Fahren macht nicht sonderlich viel Spass, denn die Maschine wechselt oft die Richtung, je nach Schlaglöchern und Steinen, die auf der Straße liegen. Die Reise kann deshalb sehr sehr lange dauern, auch wenn sie schließlich hält.

Leider weiß man weder genau, wann das passiert, noch wo; deshalb empfiehlt es sich, genügend Proviant mitzunehmen. Weil jede bessere Turing-Maschine heutzutage einen Beiwagen, einen Gepäckträger und einen ein- oder gar zweiachsigen Anhänger hat, ist das mit dem Proviant bis zu einem Zeitraum von 31,415 Wochen normalerweise auch kein Problem.

Mit Hilfe des Halteproblems kann man beweisen, dass es für jeden beliebigen Algorithmus einen gibt, der noch langsamer ist (Das gilt nicht für Kamele, siehe: Langsamkeitssatz).

Manche Turingmaschinen lösen das Halteproblem an einer Mauer.