\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\SPACE}{\textnormal{SPACE}} \)

Übungsaufgabe Entwerfen Sie eine platzbeschränkte Turingmaschine mit keinem Schreib-Lese-Band, die folgende Funktion berechnet: Auf Eingabe $x \in \{0,1\}^*$ soll sie $x + 1$ ausgeben; also $x$ als natürliche Zahl in Binärdarstellung interpretieren; darauf $1$ addieren; das Ergebnis in Binärdarstellung ausgeben.

  • Einfach: Nehmen Sie an, dass wir die Zahlen "umgekehrt" darstellen, also mit least significant bit zur Linken, also $12$ als $0011$ und das Ergebnis
  • Schwieriger: Zeigen Sie, wie das geht, wenn Eingabe und Ausgabe mit most significant bit zur Linken geschrieben werden, also die $12$ als $1100$ dargestellt wird.

Übungsaufgabe (Ein bisschen schwierig). Zeigen Sie $\SPACE(1) = $ Regular. In Worten: sei $L$ eine Sprache, die wir ohne jeden zusätzlichen Speicher entscheiden können, also mit einer Turingmaschine $M$, die nur ein Band hat (das Eingabeband) und darauf nur lesen kann; dann ist $L$ regulär!

Hinweis: Beachten Sie, dass sich $M$ im Gegensatz zu einem endlichen Automaten in beide Richtungen bewegen kann, nach rechts und nach links. So einfach ist es nämlich nicht!