Frage zu MuLö 8.2 (3)

Benutzeravatar
kahler
Computerversteher
Computerversteher
Beiträge: 351
Registriert: 17. Apr 2004 11:24

Frage zu MuLö 8.2 (3)

Beitrag von kahler » 22. Mär 2008 13:46

Bei der Übung 8.2, Teilaugabe 3 wird nach der Anzahl der möglichen Turingmaschinen gefragt.
Nach meinem Verständnis gibt es 2 Turingmaschinen:

\(TM_1(\{z_{start}, z_{stop}\}, z_{stop}, z_{stop}, \{\Box, 1\}, \Box, \{1\}, \delta)\)

\(TM_1(\{z_{start}, z_{stop}\}, z_{start}, z_{stop}, \{\Box, 1\}, \Box, \{1\}, \delta)\)

Der Definitions- sowie Bildbereich von der Übergangsfunktion ist für beide TM gleich.

\($Def(\delta) = \{Z \backslash z_{stop}\} \times \Gamma = \{z_{start}\} \times \{\Box, 1\} \\ \Rightarrow |Def(\delta)| = 2$\)

\($Bild(\delta) = Z \times \Gamma \times \{\hookleftarrow, \circlearrowleft, \hookrightarrow\} = \{z_{start}, z_{stop}\} \times \{\Box, 1\} \times \{\hookleftarrow, \circlearrowleft, \hookrightarrow\} \\ \Rightarrow |Bild(\delta)| = 12$\)

Also müsste es doch \($2 \times 2 \times 12 = 48$\) verschiedene Turingmaschinen geben.

In der Musterlösung allerdings wird von \($12 \times 12 = 144\) Turingmaschinen gesprochen.

Wo liegt hier mein Denkfehler?
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d- s:+ a-- C++++ UL++++$ P+>+++ L++ E--- W+++$ N+ o+ K? w O M V- PS+ PE++ Y+ PGP- t--- 5--- X-- R tv b DI++ D+ G e h r y?+
------END GEEK CODE BLOCK------

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Frage zu MuLö 8.2 (3)

Beitrag von Simon Siegler » 25. Mär 2008 09:21

Sie haben ja schon die Mächtigkeiten von Definitions- und Bildbereich korrekt bestimmt. Die Menge der Abbildungen hat dann gerade die Mächtigkeit \(|Bild^{Def}|\) was im Fall endlicher Mengen eben \(|Bild|^{|Def|}\) entspricht.

Im Übrigen bin ich davon ausgegangen, dass Endzustand und Startzustand verschieden sind. Andernfalls kommt zu den 144 noch die eine Maschine mit nur einem Zustand hinzu.

Antworten

Zurück zu „Archiv“