Kann mir jemand helfen, ich kopiere die Aufgabestellung nicht ganz, und zwar an dieser Stelle:

"Verwenden Sie eine Mehrband-Turing-Maschine mit zwei Arbeitsbändern, bei deren Zustandsdiagramm eine Kante
….
bedeutet, dass die 2-NTM vom Zustand z1 in den Zustand z2 übergeht, falls unter dem LSK-1 (bzw. LSK-2) das Symbol a (bzw. c) steht und dabei durch das Symbol b (bzw. d) ersetzt wird …"

Soll das heißen, dass die TM in den nächsten Zustand übergeht, wenn unter dem LSK-1 a UND unter dem LSK-2 c steht?
Oder wird's gemeint, dass der Übergang auch dann stattfindet, wenn z.B unter dem LSK-1 a und unter dem LSK ein von c verschiedenes Symbol steht?

ne das heißt schon das bei einem Übergang genau angegeben ist,
welche beiden Buchstaben auf den beiden Bändern stehen (z.B. a und c),
und danach 2 andere (oder gleiche) Buchstaben wieder hingeschrieben werden,

ich hab da auch gleich ne Gegenfrage:
wo steht denn das Eingabewort bei dieser Art Turingmaschine?
auf dem ersten Band?

und auf dem 2. steht zu Beginn nichts?

gibts kein spezielles Ein-/ Ausgabeband?
soll die Ausgabe wenn denn welche wäre, auf Band 1 oder 2?

Ich glaub bei ner Mehrband-TM kann davon ausgegangen werden, dass das Eingabewort auf dem ersten Arbeitsband steht, während die übrigen Arbeitsbänder leer sind; also so, wie du schon dachtest.
-bj

ich bin auch der Meinung, dass das Eingabewort auf dem 1.Band stehen müsste, und auf dem 2. zu Beginn nichts.

Da man auf dem 1.Band schreiben darf, ist es dann kein Eingabeband.
Ich denke, es soll keine spezielle Ein-/ Ausgabebänder geben.
Sicher bin ich mir jedoch nicht.

Frage:
Wann ist eine 2-TM nicht determenistisch?

Muss es bei einem Übergang unter beiden LSK gleiche Symbole stehen?

Oder ist sie es schon, wenn unter dem LSK-1 das gleiche steht, unabhängig davon was unter dem LSK-2 ist.

du musst aus der gleichen Situation der TM aus 2 Möglichkeiten haben,
also 2 Pfeile mit gleichen Ausgangszustand und gleichen Symbolen auf den beiden Bändern,
die unterschiedliches bewirken