{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Turingmaschine – Notebook\n",
    "\n",
    "**Informatik 12 · Grundlagen**\n",
    "\n",
    "Im Heft steht die Turingmaschine als Tabelle. Hier bauen Sie sie als Programm — in\n",
    "knapp zwanzig Zeilen. Danach schreiben Sie eigene Maschinen und messen, wie teuer\n",
    "das Rechnen auf einem Band ist.\n",
    "\n",
    "Das Band ist ein `dict`: Es bildet Positionen auf Zeichen ab, und wo nichts steht,\n",
    "gilt das Leerzeichen. So ist es nach beiden Seiten unendlich, ohne dass wir uns\n",
    "um die Länge kümmern müssen.\n",
    "\n",
    "Führen Sie zuerst die nächste Zelle aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "LEER = \"_\"\n",
    "\n",
    "# Die Maschine aus Abschnitt 1.2.1: unaere Addition.\n",
    "# Schluessel (Zustand, gelesenes Zeichen) -> (geschrieben, Bewegung, neuer Zustand)\n",
    "ADDIEREN = {\n",
    "    (\"q0\", \"1\"):  (\"1\", \"R\", \"q0\"),\n",
    "    (\"q0\", \"+\"):  (\"1\", \"R\", \"q1\"),\n",
    "    (\"q1\", \"1\"):  (\"1\", \"R\", \"q1\"),\n",
    "    (\"q1\", LEER): (LEER, \"L\", \"q2\"),\n",
    "    (\"q2\", \"1\"):  (LEER, \"N\", \"qa\"),\n",
    "}\n",
    "\n",
    "\n",
    "def band_aus(text):\n",
    "    \"\"\"Macht aus einer Zeichenkette ein Band {Position: Zeichen}.\"\"\"\n",
    "    return {i: zeichen for i, zeichen in enumerate(text)}\n",
    "\n",
    "\n",
    "def band_text(band):\n",
    "    \"\"\"Gibt den beschriebenen Teil des Bandes als Zeichenkette zurueck.\"\"\"\n",
    "    if not band:\n",
    "        return \"\"\n",
    "    stellen = sorted(band)\n",
    "    return \"\".join(band.get(i, LEER) for i in range(stellen[0], stellen[-1] + 1))\n",
    "\n",
    "\n",
    "def zeige(band, kopf, zustand):\n",
    "    \"\"\"Eine Zeile wie im Heft: Zustand, Band, Kopf in eckigen Klammern.\"\"\"\n",
    "    stellen = sorted(band) or [kopf]\n",
    "    von, bis = min(stellen[0], kopf), max(stellen[-1], kopf)\n",
    "    teile = []\n",
    "    for i in range(von, bis + 1):\n",
    "        zeichen = band.get(i, LEER)\n",
    "        teile.append(\"[\" + zeichen + \"]\" if i == kopf else \" \" + zeichen + \" \")\n",
    "    print(zustand.ljust(4), \"\".join(teile))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 1 · Ein einzelner Schritt\n",
    "\n",
    "Schreiben Sie `schritt`: Die Funktion liest das Zeichen unter dem Kopf, sucht die\n",
    "passende Regel, schreibt das neue Zeichen auf das Band und bewegt den Kopf.\n",
    "\n",
    "Sie gibt `(neuer_zustand, neue_kopfposition)` zurück — oder `None`, wenn es keine\n",
    "Regel gibt. Das Band wird dabei verändert, das ist Absicht.\n",
    "\n",
    "**Frage:** Warum braucht die Funktion kein Ende-Kriterium, sondern nur „es gibt keine Regel“?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def schritt(regeln, zustand, band, kopf):\n",
    "    \"\"\"Fuehrt einen Schritt aus. Gibt (zustand, kopf) zurueck oder None.\"\"\"\n",
    "    zeichen = band.get(kopf, LEER)\n",
    "    # TODO: Regel nachschlagen; wenn es keine gibt, None zurueckgeben\n",
    "    # TODO: Zeichen schreiben, Kopf je nach R / L / N bewegen\n",
    "    return None\n",
    "\n",
    "\n",
    "# band = band_aus(\"11+111\")\n",
    "# zeige(band, 0, \"q0\")\n",
    "# print(schritt(ADDIEREN, \"q0\", band, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 2 · Die Maschine laufen lassen\n",
    "\n",
    "`ausfuehren` startet im Anfangszustand auf Position 0 und macht Schritte, bis keine\n",
    "Regel mehr passt. Mit `zeigen=True` soll nach jedem Schritt eine Zeile ausgegeben\n",
    "werden — genau die Darstellung aus dem Heft.\n",
    "\n",
    "Die Obergrenze `grenze` ist kein Schönheitsfehler, sondern Notwehr: Eine\n",
    "Turingmaschine darf endlos laufen, Ihr Notebook soll es nicht.\n",
    "\n",
    "**Frage:** Für `11+111` nennt das Heft acht Schritte. Kommt Ihr Programm auf dieselbe Zahl? Zählen Sie nach, was dabei als „ein Schritt“ gilt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ausfuehren(regeln, text, start=\"q0\", grenze=500, zeigen=False):\n",
    "    \"\"\"Laesst die Maschine laufen. Gibt (band, zustand, schritte) zurueck.\"\"\"\n",
    "    band, kopf, zustand, schritte = band_aus(text), 0, start, 0\n",
    "    if zeigen:\n",
    "        zeige(band, kopf, zustand)\n",
    "    # TODO: so lange schritt() aufrufen, bis None zurueckkommt oder\n",
    "    #       grenze erreicht ist; dabei schritte mitzaehlen\n",
    "    return band, zustand, schritte\n",
    "\n",
    "\n",
    "# band, zustand, n = ausfuehren(ADDIEREN, \"11+111\", zeigen=True)\n",
    "# print(n, \"Schritte, Ergebnis:\", band_text(band).count(\"1\"), \"Striche\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 3 · Eine eigene Maschine: Parität\n",
    "\n",
    "Schreiben Sie die Regeln einer Maschine, die ein Wort aus Nullen und Einsen liest\n",
    "und hinten eine `1` anhängt, wenn die Anzahl der Einsen **ungerade** ist, sonst\n",
    "eine `0`.\n",
    "\n",
    "Der Trick ist derselbe wie beim Automaten in Kapitel 5: Der Zustand merkt sich\n",
    "nicht, wie viele Einsen gelesen wurden, sondern nur, ob es bisher gerade oder\n",
    "ungerade viele waren.\n",
    "\n",
    "**Frage:** Wie viele Zustände brauchen Sie — und warum reichen so wenige, obwohl das Wort beliebig lang sein darf?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PARITAET = {\n",
    "    # TODO: Regeln eintragen.\n",
    "    # Vorschlag fuer die Namen: qg = bisher gerade, qu = bisher ungerade\n",
    "}\n",
    "\n",
    "\n",
    "# for wort in [\"\", \"0\", \"1\", \"1011\", \"110011\"]:\n",
    "#     band, zustand, n = ausfuehren(PARITAET, wort, start=\"qg\")\n",
    "#     print(wort.ljust(8), band_text(band), \"->\", band_text(band)[-1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 4 · Was Rechnen auf einem Band kostet\n",
    "\n",
    "Die Maschine für $a^n b^n$ aus Abschnitt 1.2.2 ist unten eingetragen. Lassen Sie\n",
    "sie für $n = 1, 2, 3, \\dots, 7$ laufen und notieren Sie die Zahl der Schritte.\n",
    "\n",
    "Teilen Sie anschließend jede Schrittzahl durch $n^2$.\n",
    "\n",
    "**Frage:** Welche Größenordnung zeigt sich? Vergleichen Sie Ihr Ergebnis mit den Begriffen aus Abschnitt 4.3.2 — und überlegen Sie, woher der Aufwand kommt: Was tut die Maschine die ganze Zeit?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ANBN = {\n",
    "    (\"q0\", \"a\"):  (\"X\", \"R\", \"q1\"),\n",
    "    (\"q0\", \"Y\"):  (\"Y\", \"R\", \"q3\"),\n",
    "    (\"q0\", LEER): (LEER, \"N\", \"qa\"),\n",
    "    (\"q1\", \"a\"):  (\"a\", \"R\", \"q1\"),\n",
    "    (\"q1\", \"Y\"):  (\"Y\", \"R\", \"q1\"),\n",
    "    (\"q1\", \"b\"):  (\"Y\", \"L\", \"q2\"),\n",
    "    (\"q2\", \"a\"):  (\"a\", \"L\", \"q2\"),\n",
    "    (\"q2\", \"Y\"):  (\"Y\", \"L\", \"q2\"),\n",
    "    (\"q2\", \"X\"):  (\"X\", \"R\", \"q0\"),\n",
    "    (\"q3\", \"Y\"):  (\"Y\", \"R\", \"q3\"),\n",
    "    (\"q3\", LEER): (LEER, \"N\", \"qa\"),\n",
    "}\n",
    "\n",
    "\n",
    "def probe(n):\n",
    "    \"\"\"Laesst ANBN auf a hoch n b hoch n laufen.\"\"\"\n",
    "    band, zustand, schritte = ausfuehren(ANBN, \"a\" * n + \"b\" * n, grenze=5000)\n",
    "    return zustand, schritte\n",
    "\n",
    "\n",
    "# TODO: fuer n von 1 bis 7 Schritte ausgeben, dazu schritte / n**2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 5 · Verdoppeln\n",
    "\n",
    "Bauen Sie eine Maschine, die eine unär geschriebene Zahl verdoppelt: Aus `111`\n",
    "soll `111111` werden.\n",
    "\n",
    "Eine mögliche Idee: Streichen Sie einen Strich links (als `X`), laufen Sie ans\n",
    "rechte Ende und hängen Sie dort einen neuen Strich an (als `Y`), laufen Sie zurück\n",
    "zum letzten `X` und machen Sie weiter. Sind alle Striche gestrichen, wandeln Sie\n",
    "alle `X` und `Y` wieder in `1` um.\n",
    "\n",
    "**Frage:** Ihre Maschine läuft ständig hin und her. Wie viele Schritte braucht sie ungefähr für die Zahl $n$? Messen Sie es, statt zu raten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "VERDOPPELN = {\n",
    "    # TODO: Regeln eintragen\n",
    "}\n",
    "\n",
    "\n",
    "# for n in range(1, 6):\n",
    "#     band, zustand, schritte = ausfuehren(VERDOPPELN, \"1\" * n, grenze=5000)\n",
    "#     print(n, \"->\", band_text(band).count(\"1\"), \"Striche in\", schritte, \"Schritten\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Abgabe\n",
    "\n",
    "Fertig ist das Notebook, wenn es von oben nach unten fehlerfrei durchläuft, die\n",
    "Addition acht Schritte braucht, die Paritätsmaschine alle fünf Testwörter richtig\n",
    "beantwortet und `VERDOPPELN` für $n = 1 \\dots 5$ jeweils $2n$ Striche liefert.\n",
    "\n",
    "Schreiben Sie unter jede Regeltabelle eine Zeile, was der jeweilige Zustand sich merkt."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
