Turingmaschinenkonstruktion

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Druckversion

Farm-Fresh brain.png   Vorwissen

Bevor du hier loslegst, solltest du die folgenden Bausteine zuvor durchgearbeitet haben:

Farm-Fresh pencil add.png   Aufgabe

Konstruiere für folgende Aufgaben eine Turingmaschine mit dem Alphabet \Sigma=\{0,1\}

  1. Jede 0 auf dem Band soll durch eine 1 überschrieben werden (und umgekehrt).
  2. Das Eingabewort soll am Ende gespiegelt werden (es soll also ein Palindrom erzeugt werden).
  3. Zu einer gegebenen Binärzahl soll 1 addiert werden.