Entscheidbarkeit der Platzbeschraenkung

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Entscheidbarkeit der Platzbeschraenkung
Hallo.

Ich habe kuerzlich im Braindump WS10 eine schoene Frage gefunden. Es ging um die Sprache aller Goedelnummern der TM’s, welche log(|w|) Zustaende besitzen. w ist hier die Goedelnummer. Offensichtlich ist die Sprache entscheidbar, da die Anzahl der Zustaende aus der Goedelnummer heraus lesbar ist. Doch wie sieht die Lage aus, wenn man das Wort “Zustaende” durch “Konfigurationen” ersetzt?
Offensichtlich kann die Sprache dann nicht mehr entscheidbar sein, weil die Platzbeschraenktheit jeder TM bekannt sein muesste. Kennt man die Platzbeschraenktheit einer TM M, so kann man wie in einer der ersten Bonusaufgaben des Semesters bewiesen ueber die Anzahl der moeglichen Konfigurationen fuer jede Eingabe entscheiden, ob sie haelt, indem man entsprechend viele Schritte simuliert und dann guckt, ob sie bis dahin haelt.

Nun Frage ich mich, offensichtlich ist der Platzverbrauch nicht aus der Goedelnummer heraus analysierbar, denn sonst waere ja das allgemeine Halteproblem H entscheidbar. Ich frage mich aber, ob man nicht zumindest potenzielle Endlosschleifen erkennen kann. Also zB die Moeglichkeit, dass eine gegebene Turingmaschine irgendwann endlos den Kopf nach rechts bewegt.
Ist dies moeglich? Ich vermute mal stark Nein, aber zumindest fuer manche TM’s ist das ja erkennbar, zB wenn diese nur einen Zustand haben, der ewig nach rechts wandert.

Das ganze haengt ja eng mit dem Halteproblem zusammen.
Daher wage ich nun den mutigen Schluss zu ziehen, dass die Sprache der Goedelnummern der Turingmaschinen, welche potenzielle Endlosschleifen drehen koennen, rekursiv aufzaehlbar ist?

Die Frage ist nicht so richtig klausurrelevant, die Antwort wuerde mich persoenlich aber sehr interessieren.

1 Like

Ich glaube, du muesstest die Sprache genauer definieren. Besteht die Sprache aus Goedelnummer und Eingabe? Oder alle
Goedelnummern, welche fuer irgendeine Eingabe eine Endlosschleife machen?

Wir wissen, dass Σ*\H nicht r.a. ist und nicht ausschliesslich Goedelnummer beinhaltet. Allerdings koennte man den ‘Muell’ ohne
Probleme rausfiltern (Syntaxanalyse) womit die dadurch entstandene Sprache L = { x | M gestartet mit x haelt nicht }
uebrig bleibt, welche nicht r.a. sein kann, da sonst auch Σ*\H r.a. waere und H entscheidbar.
Falls deine Sprache S = { | Es gibt ein x, so dass x \in L } (Alle Goedelnummern, welche fuer irgendeine Eingabe
nicht halten) ist. Dann ist diese auch nicht r.a…


Danke fuer die Antwort.

Ich meine nur die Goedelnummern.
Worum es mir geht ist:
Kann ich am Quellcode erkennen, ob ein gegebenes Programm potenziell ueberhaupt Endlosschleifen erzeugen kann?
Also zB die zu

int main() {
return 0;
}

aequivalente TM wird fuer keine Eingabe eine Endlosschleife produzieren.
Kann ich alle Arten von Programmen, welche einen “festen” Ablauf haben, am Quellcode erkennen?


Das waere dann die Frage, ob die Sprache, welche fuer alle Eingaben haelt, r.a. ist ? Ich bezweifle es, aber mir faellt formaler Beweis ein.


So formuliert liegt die Antwort auf der Hand. Danke.