Komplexitätstheorie (3) - Turing-Maschinen mit minimalistischem Alphabet

[Sone]

Behauptung:
For every $f : \{0, 1\}^* \rightarrow \{0, 1\}$ and time constructible $T : \mathbb{N} \rightarrow \mathbb{N}$, if f is computable in time T(n) by a TM M using alphabet Γ, then it is computable in time $4 log |\Gamma| T(n)$ by another TM N using the alphabet {0, 1, [Start-Symbol], [Blank-Symbol]}.

Ich weiß nicht, wie man ein Viereck oder ein Dreieck mit Latex o.ä. darstellt. Oder ein großes M mit Tilde.

Gut, der Beweis müsste an sich so aussehen:

In einem Schritt von M wird folgendes getan:

• Es wird von allen k Tapes ein Symbol gelesen.
• Es wird ein neuer State gesetzt.
• Es werden k-1 Symbole auf alle Tapes außer dem Input-Tape geschrieben.
• Es werden alle Köpfe bewegt (oder auch nicht bewegt).

Das beinhaltet das Aufrufen der Transitions-Funktion.
Die Maschine N muss indes erst einmal alle Symbole einlesen, das sind $log |\Gamma| T(n)$ Schritte.
Nun muss sie alle Symbole schreiben, das sind $log |\Gamma| T(n)$, dann wiederum muss sie alle Köpfe bewegen, wiederum höchstens $log |\Gamma| T(n)$ Schritte. Wenn man es also knapp hält, $3 log |\Gamma| T(n)$.

Ohne jetzt die genaue Transitionsfunktion oder die State-Menge zu definieren - habe ich noch irgendwas versäumt? Oder war's das von der Idee schon?

Danach kommt noch die Behauptung mit einem Tape statt k, und danach das "Umknicken" einer bidirektionalen Turing-Maschine in eine unidirektionale.

Danke im Voraus

[otze]

State wechseln ist auch noch irgendwie relevant :). Du solltest schon auf das Ergebnis kommen.

[knivil]

Wenn die Aufgaben aus einem Buch sind, dann besorg dir das Loesungsheft. In meinen Vorlesungen war sowas bloedes nie relevant.

Ich weiß nicht, wie man ein Viereck oder ein Dreieck mit Latex o.ä. darstellt. Oder ein großes M mit Tilde.

Ist doch egal, es sind nur Symbole.

[Sone]

Ich glaube, ich weiß jetzt wieso im Buch vier statt drei mal $log |\Gamma| T(n)$ herauskommt.
Zum Schreiben muss man eventuell den Kopf wieder an die Anfangsposition bewegen.

Also nach meiner Formulierung schreibt der Kopf rückwärts:

|1101|1010|0001|
      ^

Der Kopf liest jetzt ein Zeichen....

|1101|1010|0001|
         ^

Jetzt muss er ein Zeichen schreiben...

|1101|0101|0001|
      ^

Und jetzt bspw. den Kopf nach links bewegen.

|1101|1010|0001|
 ^

Also $3 log |\Gamma| T(n)$.

Mit Vorwärts-Schreiben:

|1101|1010|0001|
      ^

Der Kopf liest jetzt ein Zeichen....

|1101|1010|0001|
         ^

Jetzt muss er ein Zeichen schreiben...

|1101|1010|0001|
      ^
|1101|1010|0001|
         ^

Und jetzt bspw. den Kopf nach links bewegen.

|1101|1010|0001|
      ^
|1101|1010|0001|
 ^

Also etwas weniger als $5 log |\Gamma| T(n)$ Schritte, aber das ist zu viel. Daher muss man Rückwärts-Schreiben nehmen.

otze schrieb:

State wechseln ist auch noch irgendwie relevant :). Du solltest schon auf das Ergebnis kommen.

State-Wechseln geschieht im letzten Schritt zum Schreiben. Das müsste doch funktionieren.

knivil schrieb:

Wenn die Aufgaben aus einem Buch sind, dann besorg dir das Loesungsheft. In meinen Vorlesungen war sowas bloedes nie relevant.

Das habe ich bereits einmal verlinkt:
Computational Complexity | ISBN: 0521424267
Es gibt für einige Aufgaben Lösungen hinten im Buch, aber nicht für diese. Anscheinend ist sie nicht interessant.
Das ist aber erst die zweite Aufgabe für Kapitel 1, es kommen noch viel mehr, darunter auch interessante. Ich mache aber brav alle durch.

Ich weiß nicht, wie man ein Viereck oder ein Dreieck mit Latex o.ä. darstellt. Oder ein großes M mit Tilde.

Ist doch egal, es sind nur Symbole.

Hast Recht, ich wollte nur die Aufgabe penibel genau abzeichnen.