Entwerfen Sie eine Turingmaschine, welche als Eingabe ein Wort $w \in\{0,1\}^*$ bekommt,…
- User
Entwerfen Sie eine Turingmaschine, welche als Eingabe ein Wort bekommt, dieses als binär kodierte Zahl interpretiert und die Zahl berechnet und ausgibt. Für und soll Ihre TM auch 0 ausgeben. Schreibe die Uebergaenge in einer Tabelle.
Schreibe die Turing-Maschine in der Form:
- anzahl von Zustanden 01 - Eingabealphabet 01B - Bandalphabet
- Startzustand
- Endzustand Uebergaenge : Zustand Eingabe Zustand Schreibe Bewegen
- Assistant
Um eine Turingmaschine zu entwerfen, die ein binäres Wort ( w \in {0,1}^* ) als Eingabe erhält, dieses als binär kodierte Zahl interpretiert und die Zahl ( \lceil \log_2 w \rceil ) berechnet und ausgibt, gehen wir wie folgt vor:
Komponenten der Turingmaschine
- Anzahl der Zustände: 6
- Eingabealphabet: {0, 1}
- Bandalphabet: {0, 1, B, X, Y} (B steht für Blank, X und Y sind Hilfssymbole)
- Startzustand: ( q_0 )
- Endzustand: ( q_6 )
Beschreibung der Zustände
- ( q_0 ): Startzustand. Überprüft, ob die Eingabe leer ist oder nur '0' enthält.
- ( q_1 ): Zählt die Anzahl der Bits im Wort.
- ( q_2 ): Überprüft, ob das Wort eine Potenz von 2 ist (nur eine '1' und restliche '0').
- ( q_3 ): Berechnet ( n ) (Anzahl der Bits) oder ( n-1 ) basierend auf der Potenzprüfung.
- ( q_4 ): Schreibt das Ergebnis auf das Band.
- ( q_6 ): Akzeptierender Endzustand.
Übergangstabelle
Zustand Eingabe Neuer Zustand Schreibe Bewegung ( q_0 ) B ( q_6 ) B R ( q_0 ) 0 ( q_6 ) 0 R ( q_0 ) 1 ( q_1 ) X R ( q_1 ) 0 ( q_1 ) 0 R ( q_1 ) 1 ( q_1 ) 1 R ( q_1 ) B ( q_2 ) B L ( q_2 ) 0 ( q_3 ) 0 L ( q_2 ) X ( q_3 ) X R ( q_2 ) Y ( q_6 ) Y R ( q_3 ) X ( q_4 ) X R ( q_3 ) 0 ( q_4 ) 0 R ( q_3 ) 1 ( q_5 ) Y L ( q_4 ) B ( q_6 ) 1 L ( q_5 ) Y ( q_6 ) 1 L ( q_6 ) * HALT * - Funktionsweise
-
Startzustand ( q_0 ):
- Wenn das Band leer (B) ist oder nur eine '0' enthält, wird 0 ausgegeben und die Maschine hält.
- Bei '1' beginnt die Zählung der Bits, markiert die erste '1' mit X und wechselt zu ( q_1 ).
-
Zählen der Bits ( q_1 ):
- Die Maschine bewegt sich nach rechts und zählt die Anzahl der Bits, bis sie ein Blank (B) erreicht.
- Wechselt dann zu ( q_2 ), um zu überprüfen, ob das Wort eine Potenz von 2 ist.
-
Überprüfung auf Potenz von 2 ( q_2 ):
- Wenn nach der ersten '1' nur '0's folgen, ist das Wort eine Potenz von 2.
- Falls weitere '1's gefunden werden, ist es keine Potenz von 2.
-
Berechnung des Ergebnisses ( q_3 ) und ( q_4 ):
- Abhängig davon, ob das Wort eine Potenz von 2 ist, wird ( n-1 ) oder ( n ) berechnet.
- Das Ergebnis wird schließlich auf das Band geschrieben und die Maschine hält.
Diese Turingmaschine zählt effektiv die Anzahl der Bits der Eingabe und bestimmt, ob die eingegebene binäre Zahl eine Potenz von 2 ist, um entsprechend ( \lceil \log_2 w \rceil ) zu berechnen und auszugeben.