Nichtdet. bei Tuningmaschinen Infobuch S. 102

Question

Guten Tag,

zu Beginn von Kapitel 3.1, S. 102 wird die ndetTM eingeführt. Meine Frage richtet sich an die ndet Zustandsübergangsfunktion:

delta(s, b) =  {(s1, b1, X1),..., (sm, bm, Xm)} (= Potenzmenge(S x B  {R, L, N})

 

Warum wird hier Potenzmenge gebildet? Ist es nicht ausreichend das Kartesische Produkt zu bilden? Darin sind doch bereits alle möglichen Tupel enthalten oder täusche ich mich?

 

Vielen Dank im voraus!

Answer 1

Nein, es muss schon die Potenzmenge sein. Ich weiß nicht genau, wie Sie das mit dem kartesischen Produkt meinen (vielleicht können Sie das noch etwas genauer ausführen), aber es geht darum, dass für jeden Übergang eine beliebige Teilmenge aller möglichen Tupel $(s, b, X) \in S \times B \times \{R, L, N\}$ angegeben werden kann (von denen dann eines während der Rechnung nichtdeterministisch ausgewählt wird).

Wenn wir beispielsweise zwei Zustände $S=\{s_1, s_2\}$ und zwei Bandzeichen $B=\{1, \star\}$ haben, dann ergeben sich folgende theoretisch mögliche Tupel für jeden Übergang:
$$S \times B \times \{R, L, N\} =
\begin{array}{l}
\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L), (s_2, \star, L),  \\
(s_1, 1, R), (s_2, 1, R),(s_1, \star, R),(s_2, \star, R),  \\
(s_1, 1, N), (s_2, 1, N),(s_1, \star, N),(s_2, \star, N)\}
\end{array}$$
Nun kann jede belibige Teilmenge dieser Menge für einen Übergang genommen werden. Das könnte beispielsweise $\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L)\}$ sein oder $\{(s_1, 1, L), (s_1, 1, N), (s_2, \star, R)\}$ oder auch einfach die leere Menge $\emptyset$.

Die Menge all dieser Teilmengen, aus denen für die Definition des Übergangs ausgewählt werden darf (durch Sie als Ersteller der Turingmaschine), ist aber gerade die Potenzmenge:
$$\wp(S \times B \times \{R, L, N\})$$

Der nichtdeterministische Rechenprozess wählt dann während der Rechnung aus der Menge, die Sie für den Übergang definiert haben, ein einzelnes Tupel aus, mit dem weitergerechnet wird. (Etwa aus der Menge $\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L)\}$ das Tupel $(s_1, \star, L)$ oder so...)

(Das kartesische Produkt der Menge $S \times B \times \{R, L, N\}$ mit sich selbst, also $(S \times B \times \{R, L, N\})\times(S \times B \times \{R, L, N\})$, würde ja lauter Paare $\left(\left(s_1, 1, L\right), \left(s_1, 1, L\right)\right)$ usw. enthalten, das ist hier nicht hilfreich.)

Comments

Ich hoffe, dass es damit klarer wird. Dieser Teil ist natürlich für das intuitive Verständnis eine der größten Herausforderungen der theoretischen Informatik. Zögern Sie nicht sich zu melden, wenn es weiterhin Schwierigkeiten gibt!

---

Vielen Dank für die schnelle und ausführliche Antwort! Mir ist jetzt klar, wo mein Denkfehler lag.