Linear beschränkte Turingmaschine

Wissenschaft Informatik
#1

Hallo!
Laut Wikipedia „kann eine linear beschränkte Turingmaschine ein um einen konstanten Faktor c größeres Band simulieren, indem das Bandalphabet c-Tupel des Eingabealphabetes enthält“ (http://de.wikipedia.org/wiki/Linear_beschr%C3%A4nkte…).

Diese Aussage ist für mich nicht logisch. Warum sollte der Bandinhalt nun auch aus dem gesamten Eingabealphabet bestehen dürfen, sobald er um den Faktor c vergrößert wurde und nicht, wie standardmäßig, wenn n Felder des Bandes benutzt werden, nur aus Zeichen des Bandalphabets?
Also: Sobald das Band c*n Felder lang ist, ist das Bandalphabet = Eingabealphabet. Warum?

Gruß und danke

#2

Nunja, das Bandalphabet kann man definieren, wie man möchte. Tupel bieten sich an, so bekomt man quasi ein mehrdimensionales Array. Stell dir vor, du hast als Bandalphabet nur 0 oder 1. Wenn du das Bandalphabet auf Paare/2-tupel erweiterst, hast du als Buchstaben {(0,0), (0,1), (1,0), (1,1)}. Schreibe sie übereinander, dann kann dein Band der Länge 4 so aussehen
0011
1011
mit den Elementen (0,1), (0,0), (1,1), (1,1), als ob du 2 Bänder übereinander hättest, also 2-facher Bandinhalt.

Nun musst du die Turingmaschine natürlich so bauen, dass es mit solchen „Buchstaben“ zurecht kommt.

Achso, keine Paare sondern k-tupel — k-facher Bandinhalt

gruss, mofte

#3

Okay, danke, das mit den Tupeln verstehe ich jetzt. Allerdings ist mir nicht klar, warum man das Bandalphabet beliebig definieren kann, wenn ein Automat mit Bandalphabet und Eingabealphabet festgelegt ist.
Es wird doch zusätzlich Rechenkraft gewonnen, wenn das Bandalphabet erweitert wird, was laut der Aussage auf meinem Arbeitsblatt nicht der Fall ist („Um zu verdeutlichen, dass man damit [Turingmaschine, die c*n Stellen des Bandes besuchen darf] gegenüber den linear bandbeschränkten TMen keine zusätzliche Rechenkraft gewonnen hat…“).

Gruß und danke

#4

Das Bandalphabet kann völlig verschieden sein vom Eingabealphabet.
Oft setzt man beide gleich, um das Modell zu vereinfachen.

Im Prinzip kann das Bandalphabet ja beliebig gewählt werden.
Wenn das Eingabealphabet {0,1} ist kann das Bandalphabet also ohne Probleme als {00,01,10,11} gewählt werden.
Dann kann man im Vergleich zu einer Turingmaschine mit Bandalphabet {0,1} um den Faktor 2 mehr Symbole der Eingabe speichern.

Was Wikipedia sagen will. Wenn die länge des Bandes gegeben ist, kann man durch geeignete Wahl des Bandalphabets ein beliebiges, endliches, Vielfaches der Bandlänge an Eingabe-Symbolen auf dem Band Speichern.

Wenn mehrere Zeichen in einem Bandsymbol gespeichert werden verkompliziert sich natürlich die Steuerung der Turingmaschine.

Hoffe das hilft Dir weiter.