F_GXdx
Captain
- Registriert
- März 2006
- Beiträge
- 4.028
Hallo,
Ich poste jetzt mal hier, da es hier wohl am besten reinpasst. Ich brauche jemanden, der sich mit theoretischer Informatik richtig gut auskennt.
Laut meinen Unterlagen ist folgendes entscheidbar:
Für eine Turingmaschine T ist entscheidbar, ob sie für alle möglichen Eingaben (über Sigma Stern) mehr als 300 Schritte macht.
Wieso? Es gibt doch unendlich viele mögliche Eingaben. Der naive Ansatz scheint also zu scheitern, allerdings habe ich den unsicheren Hinweis, dass es doch nur endlich viele Eingaben gibt, warum?
Danke und Gruß
Noch ein Hinweis, grundsätzlich ist die Anzahl der Schritte eine triviale Eigenschaft, und fällt daher nicht dem Satz von Rice zum Opfer, der bekanntlich sagt, dass alle nicht-trivialen Eigenschaften einer Turingmaschine unentscheidbar sind.
OK, ich bin selbst drauf gekommen, und beantworte es der Vollständigkeit halber mal kurz:
Für alle Wörter der Länge >300, die nicht akzeptiert werden, ist es offensichtlich erfüllt, da alleine zum Einlesen der ersten 300 Buchstaben schön mehr als 300 Schritte notwendig sind. Für Wörter der Länge >300, die in unter 300 Schritten akzeptiert werden, reicht es die Wörter der Länge <=300 zu betrachten, da sie nur anhand ihres Präfixes schneller als die Gesamtwortlänge erkannt werden können (auch hier Argument der Leselänge). Es reicht also alle Wörter die höchstens 300 Buchstaben haben auf Halt zu untersuchen, da es keine längeren Wörter mehr geben kann die auf einmal plötzlich doch wieder einen Halt in unter 300 Schritten erzeugen. Und da Sigma endlich ist, ist auch diese Menge endlich (wenn auch möglicher Weiße extrem groß) und kann überprüft werden.
Daher ist es tatsächlich entscheidbar.
qed und close
Ich poste jetzt mal hier, da es hier wohl am besten reinpasst. Ich brauche jemanden, der sich mit theoretischer Informatik richtig gut auskennt.
Laut meinen Unterlagen ist folgendes entscheidbar:
Für eine Turingmaschine T ist entscheidbar, ob sie für alle möglichen Eingaben (über Sigma Stern) mehr als 300 Schritte macht.
Wieso? Es gibt doch unendlich viele mögliche Eingaben. Der naive Ansatz scheint also zu scheitern, allerdings habe ich den unsicheren Hinweis, dass es doch nur endlich viele Eingaben gibt, warum?
Danke und Gruß
Noch ein Hinweis, grundsätzlich ist die Anzahl der Schritte eine triviale Eigenschaft, und fällt daher nicht dem Satz von Rice zum Opfer, der bekanntlich sagt, dass alle nicht-trivialen Eigenschaften einer Turingmaschine unentscheidbar sind.
Ergänzung ()
OK, ich bin selbst drauf gekommen, und beantworte es der Vollständigkeit halber mal kurz:
Für alle Wörter der Länge >300, die nicht akzeptiert werden, ist es offensichtlich erfüllt, da alleine zum Einlesen der ersten 300 Buchstaben schön mehr als 300 Schritte notwendig sind. Für Wörter der Länge >300, die in unter 300 Schritten akzeptiert werden, reicht es die Wörter der Länge <=300 zu betrachten, da sie nur anhand ihres Präfixes schneller als die Gesamtwortlänge erkannt werden können (auch hier Argument der Leselänge). Es reicht also alle Wörter die höchstens 300 Buchstaben haben auf Halt zu untersuchen, da es keine längeren Wörter mehr geben kann die auf einmal plötzlich doch wieder einen Halt in unter 300 Schritten erzeugen. Und da Sigma endlich ist, ist auch diese Menge endlich (wenn auch möglicher Weiße extrem groß) und kann überprüft werden.
Daher ist es tatsächlich entscheidbar.
qed und close
Zuletzt bearbeitet:
