0 Daumen
177 Aufrufe

Aufgabe:

a) Geben Sie eine Turingmaschine \( T_{\text {inc }} \) (als Zeichnung) an, welche die Eingabe \( w \in \) \( \{0,1\}^{+} \)als Binärzahl auffasst und um 1 inkrementiert. Verwenden Sie höchstens 3 Zustände.

b) Geben Sie eine Turingmaschine \( T_{\text {copy }} \) (als Zeichnung) an, welche die Eingabe \( w \in \) \( \{0,1\}^{*} \) hinter ein besonderes Trennsymbol,\( -{ }^{\prime \prime} \) kopiert. Am Ende der Berechnung soll das Band (ausschließlich) \( { }_{\prime} w-w^{\prime \prime} \) beinhalten. Verwenden Sie höchstens 7 Zustände. Achten Sie auf eine übersichtliche Lösung!
Anmerkung: Teilpunkte bei Verwendung von mehr als 7 Zuständen.

c) Beschreiben Sie textuell, wie eine Turingmaschine \( T_{\mathbb{N}_{0}} \) vorgehen kann, um \( \mathbb{N}_{0} \) (gegebenenfalls in irgend einer Codierung) aufzuzählen, d.h. alle \( n \in \mathbb{N}_{0} \) (ggf. codiert), durch das Trennzeichen " " \( ^{-\prime} \) getrennt, auf das Band zu schreiben. Dabei soll die Bandbeschriftung nicht durch " \( \square \square \) unterbrochen werden. Beschreiben die Arbeitsweise der Turingmaschine präzise.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community