Die primäre Definition von Turing machine (TM), zumindest in meinem eigenen Nachschlagewerk (Hopcroft + Ullman 1979), ist deterministisch. Daher ist mein eigenes Verständnis des Halteproblems in erster Linie für deterministisches TM, obwohl mir bewusst ist, dass es für andere Arten von Automaten in...
Ich habe in Wikipedia und einigen anderen Texten gelesen, dass Das Problem des Anhaltens ist für [...] linear begrenzte Automaten (LBAs) und deterministische Maschinen mit endlichem Speicher [...] entscheidbar . Aber früher steht geschrieben, dass das Halteproblem ein unentscheidbares Problem ist...
Ich hatte den Eindruck, dass unsere Computer, da sie endlich sind, letztendlich nicht leistungsfähiger sind als (außerordentlich große) endliche Zustandsmaschinen. Linear gebundene Turing-Maschinen sind zwar auch endlich, aber es scheint, dass reguläre Sprachen streng genommen eine unangemessene...