Simple_Turing_Simulation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Turing-Maschinen-Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "von W. Conen, Version 1.0\n",
    "\n",
    "Dieses kurze Notebook gibt die Möglichkeit, eine simple Implementierung einer Variante der von \n",
    "[Alan M. Turing](https://de.wikipedia.org/wiki/Alan_Turing) entwickelten Turing-Maschinen zu erproben. Über Turing wird an\n",
    "anderem Orte, z.B. in der [Biografie von Andrew Hodges](http://www.turing.org.uk/), sehr eloquent und informativ berichtet. Seine Lebensgeschichte ist \n",
    "spannend, ergreifen und, leider, auch traurig. Seine Beiträge in der Entstehungphase der Informatik sind von grundlegender \n",
    "Bedeutung für das, was folgte."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Elementares\n",
    "\n",
    "Unsere STM (STM steht für Simple-Turing-Maschine) kann Folgendes:\n",
    "\n",
    "Sie arbeitet auf einem endlosen Band aus nebeneinander liegenden Kästchen, in denen etwas stehen kann - oder auch nicht (dann denken wir uns dort ein Leerzeichen). Alles, was auf dem Band stehen darf, stammt aus dem sogenannten Bandalphabet, z.B. könnten dort Einsen (1) und Nullen (0) erlaubt sein - und das Leerzeichen,  klar. Oft trennt man übrigens zwischen Bandalphabet und Eingabealphabet (s. die Definition einer deterministischen Turingmaschine in https://de.wikipedia.org/wiki/Turingmaschine), aber ehrlich gesagt, ist das zu 99,59% Korinthengekacke und wir können das hier ignorieren.\n",
    "\n",
    "Die STM hat einen Schreib/Lese-Kopf, der auf genau einer Bandposition steht. Wenn sich eine Eingabe auf dem Band befindet (was man sehr oft annimmt), dann unterstellt man, dass der Kopf auf dem am weitestens links stehenden Zeichen der Eingabe steht. Die Eingabe ist endlich, es gibt also immer einen \"leftmost character\".\n",
    "\n",
    "Die STM arbeitet dann ein Programm ab. Sie ist zu jedem Zeitpunkt in einem wohlbestimmten Zustand. Zu Beginn ist sie in einem ausgezeichneten Startzustand. Wenn Sie nicht bereits in einem Endzustand ist, dann liest sie das Zeichen unter ihrem Schreib/Lese-Kopf und schaut in ihrem Programm nach, was für das Paar (Zustand,Gelesenes_Zeichen) nun zu tun ist. Wenn sie in ihrem Programm keine passende Anweisung findet, bleibt Sie stehen. Im Grunde ist sie dann \"kaputt\". Wenn sie eine passende Anweisung findet, führt sie diese aus.\n",
    "\n",
    "Wie sieht so eine Ausführung aus? Die Maschine schreibt zunächst ein Zeichen an die Position, an der sie steht (immer noch die gleiche Position, an der sie \"Gelesenes_Zeichen\" las...klar), bewegt sich dann nach links (L) oder rechts (R) (manche Maschinen dürfen auch stehen bleiben (-), unsere unten auch!) und geht dabei in einen Folgezustand über. Das war's schon. Dann schaut sie an der neuen Position (die manchmal auch die alte sein kann) wieder nach dem dort stehenden Zeichen usw.\n",
    "\n",
    "Das Programm ist im übrigen auch endlich (es gibt also auch nur endlich viele Zustände), ebenso ist das (Band)alphabet endlich. \n",
    "\n",
    "Eine Berechnung, also eine technisch erfolgreiche Ausführung eines Programms, ergibt sich dann, wenn man in einen der ausgezeichneten Endzustände der Maschine gelangt (einen muss es immer mindestens geben). Dann bleibt die Maschine stehen und ist \"fertig\".\n",
    "\n",
    "Ob das erzielte Ergebnis korrekt ist oder nicht, weiß man dann noch nicht. Eine korrekte Berechnung ist es, wenn die Berechnung auch noch korrekt ist ;)\n",
    "\n",
    "Verrückt ist, dass man diese einfachen Maschine so bauen kann, das man genau das lösen kann, was man intuitiv für berechenbar hält (das ist die sogenannte Church-Turing-These).\n",
    "\n",
    "Turing hat diese Maschinen auch in einer universellen Form vorgeschlagen, die ein Programm ausführen, das in der Lage ist, eine andere Turingmaschine (jede!) zu \"simulieren\", die als Programmcode auf dem Band steht und die dann auf eine Eingabe angewendet wird. Das ist natürlich noch viel cooler - und war ein wichtiges logisches Vorbild für speicherprogrammierbare Rechnerarchitekturen (ja ja, ungefähr all das, was wir heute so im Alltag verwenden...Notebooks, Handys, Tablets...)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mini-Turing-Maschinen-Simulator\n",
    "\n",
    "Wir erläutern jetzt kurz die Nutzung des unten stehenden Programms:\n",
    "\n",
    "Die Turingmaschine startet auf dem ersten linken Zeichen der Eingabe (wenn es\n",
    "eine Eingabe gibt)- um das zu garantieren, stellen wir die Eingabe passend zur\n",
    "Verfügung.\n",
    "\n",
    "Sie befindet sich zu Beginn in einem Anfangszustand z_start (den Namen legen \n",
    "wir so fest). Die Abarbeitung ist beendet, wenn die Maschine den Zustand z_ende\n",
    "erreicht (wir erlauben unten nur einen Endzustand).\n",
    "\n",
    "Die Maschine kann Befehle im folgenden Format interpretieren:\n",
    "<pre>\n",
    "  (zustand_x,zeichen_1)->(zeichen_2,zustand_y,bewegung_b)\n",
    "</pre>\n",
    "Bedeutung: Wenn die Maschine im Zustand zustand_x das Zeichen zeichen_1\n",
    "sieht, dann schreibt sie das Zeichen zeichen_2, geht in den Zustand\n",
    "zustand_y und führt die Bewegung b aus. b kann L,R oder - sein (L für\n",
    "links, R für rechts, - für \"nicht bewegen\"). Hierbei können zustand_x und\n",
    "zustand_y auch die gleichen Zustände sein, ebenso zeichen_1 und zeichen_2.\n",
    "\n",
    "Die Befehle werden als 5-elementige Listen dargestellt mit Strings als\n",
    "Elemente:\n",
    "<pre>\n",
    "    ['z_start','0','1','z_start','R']\n",
    "</pre>\n",
    "\n",
    "Ein Programm ist eine Liste von Befehlen:\n",
    "<pre>\n",
    "  [\n",
    "    ['z_start','0','1','z_start','R'],\n",
    "    ['z_start','1','0','z_start','R'],\n",
    "    ['z_start','_','_','z_ende','L']\n",
    "  ]\n",
    "</pre>\n",
    "\n",
    "Hierbei steht _ für das Leerzeichen (oder \"Leersymbol\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Turingmaschine  Invertiere  ist im Startzustand z_start\n",
      "Die Eingabe (mit Eingabezeiger-Position):\n",
      "    -->  10110\n",
      "    -->  ^\n",
      "0 : -- Execute:  ['z_start', '1', '0', 'z_start', 'R']\n",
      "    -->  00110\n",
      "    -->   ^\n",
      "1 : -- Execute:  ['z_start', '0', '1', 'z_start', 'R']\n",
      "    -->  01110\n",
      "    -->    ^\n",
      "2 : -- Execute:  ['z_start', '1', '0', 'z_start', 'R']\n",
      "    -->  01010\n",
      "    -->     ^\n",
      "3 : -- Execute:  ['z_start', '1', '0', 'z_start', 'R']\n",
      "    -->  01000\n",
      "    -->      ^\n",
      "4 : -- Execute:  ['z_start', '0', '1', 'z_start', 'R']\n",
      "    -->  01001_____\n",
      "    -->       ^\n",
      "5 : -- Execute:  ['z_start', '_', '_', 'z_ende', 'L']\n",
      "    -->  01001_____\n",
      "    -->      ^\n",
      "ERFOLG: Die Maschine hat den Endzustand erreicht!\n",
      "\n",
      "\n",
      "Turingmaschine  Addiere_1  ist im Startzustand z_start\n",
      "Die Eingabe (mit Eingabezeiger-Position):\n",
      "    -->  10110\n",
      "    -->  ^\n",
      "0 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  10110\n",
      "    -->   ^\n",
      "1 : -- Execute:  ['z_start', '0', '0', 'z_start', 'R']\n",
      "    -->  10110\n",
      "    -->    ^\n",
      "2 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  10110\n",
      "    -->     ^\n",
      "3 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  10110\n",
      "    -->      ^\n",
      "4 : -- Execute:  ['z_start', '0', '0', 'z_start', 'R']\n",
      "    -->  10110_____\n",
      "    -->       ^\n",
      "5 : -- Execute:  ['z_start', '_', '_', 'z_1', 'L']\n",
      "    -->  10110_____\n",
      "    -->      ^\n",
      "6 : -- Execute:  ['z_1', '0', '1', 'z_ende', '-']\n",
      "    -->  10111_____\n",
      "    -->      ^\n",
      "ERFOLG: Die Maschine hat den Endzustand erreicht!\n",
      "\n",
      "\n",
      "Turingmaschine  Addiere_1  ist im Startzustand z_start\n",
      "Die Eingabe (mit Eingabezeiger-Position):\n",
      "    -->  11111\n",
      "    -->  ^\n",
      "0 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  11111\n",
      "    -->   ^\n",
      "1 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  11111\n",
      "    -->    ^\n",
      "2 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  11111\n",
      "    -->     ^\n",
      "3 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  11111\n",
      "    -->      ^\n",
      "4 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  11111_____\n",
      "    -->       ^\n",
      "5 : -- Execute:  ['z_start', '_', '_', 'z_1', 'L']\n",
      "    -->  11111_____\n",
      "    -->      ^\n",
      "6 : -- Execute:  ['z_1', '1', '0', 'z_1', 'L']\n",
      "    -->  11110_____\n",
      "    -->     ^\n",
      "7 : -- Execute:  ['z_1', '1', '0', 'z_1', 'L']\n",
      "    -->  11100_____\n",
      "    -->    ^\n",
      "8 : -- Execute:  ['z_1', '1', '0', 'z_1', 'L']\n",
      "    -->  11000_____\n",
      "    -->   ^\n",
      "9 : -- Execute:  ['z_1', '1', '0', 'z_1', 'L']\n",
      "    -->  10000_____\n",
      "    -->  ^\n",
      "10 : -- Execute:  ['z_1', '1', '0', 'z_1', 'L']\n",
      "    -->  _____00000_____\n",
      "    -->      ^\n",
      "11 : -- Execute:  ['z_1', '_', '1', 'z_ende', '-']\n",
      "    -->  ____100000_____\n",
      "    -->      ^\n",
      "ERFOLG: Die Maschine hat den Endzustand erreicht!\n",
      "\n",
      "\n",
      "Turingmaschine  Addiere_1  ist im Startzustand z_start\n",
      "Die Eingabe (mit Eingabezeiger-Position):\n",
      "    -->  _\n",
      "    -->  ^\n",
      "0 : -- Execute:  ['z_start', '_', '_', 'z_1', 'L']\n",
      "    -->  ______\n",
      "    -->      ^\n",
      "1 : -- Execute:  ['z_1', '_', '1', 'z_ende', '-']\n",
      "    -->  ____1_\n",
      "    -->      ^\n",
      "ERFOLG: Die Maschine hat den Endzustand erreicht!\n",
      "\n",
      "\n",
      "Turingmaschine  Addiere_1  ist im Startzustand z_start\n",
      "Die Eingabe (mit Eingabezeiger-Position):\n",
      "    -->  1020\n",
      "    -->  ^\n",
      "0 : -- Execute:  ['z_start', '1', '1', 'z_start', 'R']\n",
      "    -->  1020\n",
      "    -->   ^\n",
      "1 : -- Execute:  ['z_start', '0', '0', 'z_start', 'R']\n",
      "    -->  1020\n",
      "    -->    ^\n",
      "FEHLER: Maschine ist stehengeblieben!\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "version = '1.0'\n",
    "\n",
    "## This is a simple deterministic turing machine\n",
    "\n",
    "class Turing(object):\n",
    "    def __init__(self,programm,input=['_']):\n",
    "        self.programm = programm\n",
    "        self.input = input # Vorsicht...\n",
    "        self.zustand = 'z_start'\n",
    "        self.befehls_zeiger = 0\n",
    "        self.input_position = 0\n",
    "        self.end_position = len(input)-1\n",
    "\n",
    "    def get_befehl(self,zeichen,zustand):\n",
    "        # Geht sehr viel effizienter...aber hier der Einfachheit halber:\n",
    "        for befehl in self.programm:\n",
    "            if befehl[0] == zustand and befehl[1] == zeichen:\n",
    "                return befehl\n",
    "        return None\n",
    "\n",
    "    def set_zustand(self,zustand):\n",
    "        self.zustand = zustand\n",
    "\n",
    "    def get_zustand(self):\n",
    "        return self.zustand\n",
    "        \n",
    "    def read(self):\n",
    "        return self.input[self.input_position]\n",
    "\n",
    "    def write(self,char):\n",
    "        self.input[self.input_position] = char\n",
    "\n",
    "    def move(self,richtung):\n",
    "        if richtung == 'L':\n",
    "            if self.input_position == 0:\n",
    "                # Hänge vorne an\n",
    "                # Stattdessen könnten wir auch\n",
    "                # einfach input.insert(0.'_') verwenden\n",
    "                # und die end_position um eins hochsetzen\n",
    "                # aber so wird ein wenig deutlicher,\n",
    "                # das wir uns AUF einem unendlichen\n",
    "                # Band voll mit Leerzeichen (_) bewegen\n",
    "                mehr = ['_','_','_','_','_']\n",
    "                l_mehr = len(mehr)\n",
    "                self.input = mehr + self.input\n",
    "                self.end_position += l_mehr\n",
    "                self.input_position += l_mehr\n",
    "            self.input_position -= 1\n",
    "        if richtung == 'R':\n",
    "            if self.input_position == self.end_position:\n",
    "                # Hänge hinten noch etwas an\n",
    "                mehr = ['_','_','_','_','_']\n",
    "                l_mehr = len(mehr)\n",
    "                self.input = self.input + mehr\n",
    "                self.end_position += l_mehr\n",
    "            self.input_position += 1\n",
    "        if richtung == '-':\n",
    "            pass # Tue nichts\n",
    "\n",
    "    def show_input(self):\n",
    "        return ''.join(self.input)\n",
    "        \n",
    "    def show_input_pointer(self):\n",
    "        vorspann = \"\"\n",
    "        for i in range(0,self.input_position):\n",
    "            vorspann += ' '  # ineffizient, aber ok hier\n",
    "        vorspann += \"^\"\n",
    "        return vorspann\n",
    "            \n",
    "    def step(self,debug=False,count=0):\n",
    "        zeichen_1 = self.read()\n",
    "        zustand_x = self.get_zustand()\n",
    "        befehl = self.get_befehl(zeichen_1,zustand_x)\n",
    "        if not befehl:\n",
    "            print(\"FEHLER: Maschine ist stehengeblieben!\")\n",
    "            return False\n",
    "        if debug: print(count,\": -- Execute: \",befehl)\n",
    "        self.fuehre_aus(befehl)\n",
    "        if debug: print(\"    --> \", self.show_input())\n",
    "        if debug: print(\"    --> \", self.show_input_pointer())\n",
    "        zustand_y = self.get_zustand()\n",
    "        if zustand_y == 'z_ende':\n",
    "            print(\"ERFOLG: Die Maschine hat den Endzustand erreicht!\")\n",
    "            return True\n",
    "        return self.step(debug,count+1)   \n",
    "        \n",
    "    def fuehre_aus(self,befehl):\n",
    "        self.write(befehl[2])\n",
    "        self.set_zustand(befehl[3])\n",
    "        self.move(befehl[4])\n",
    "        \n",
    "## Ende des Simulators\n",
    "\n",
    "## Invertieren von 0 und 1, es wird also aus jeder 0 eine 1 und aus jeder 1\n",
    "## eine 0 gemacht\n",
    "prog_inv = [\n",
    "    ['z_start','0','1','z_start','R'],\n",
    "    ['z_start','1','0','z_start','R'],\n",
    "    ['z_start','_','_','z_ende','L']\n",
    "]\n",
    "\n",
    "## Binäres Addieren von 1 (ja ja, ich weiss, das ist eine der Lösungen...\n",
    "## schauen sie einfach nicht hin und lösen es zuerst selbst)\n",
    "\n",
    "## Wenn sie richtig fleißig sein wollen, dann arbeiten sie an einem\n",
    "## Programm, um zwei Binärzahlen, die durch ein Blank getrennt auf dem\n",
    "## Band stehen, der Kopf steht auf dem ersten Zeichen der ersten Eingabe links,\n",
    "## zu addieren. Das Ergebnis soll, wieder durch ein oder mehrere Blanks\n",
    "## getrennt, rechts von den Eingaben stehen. Die Eingaben dürfen sie dabei\n",
    "## modifizieren, wenn am Ende nur noch das Ergebnis auf dem Band steht, ist\n",
    "## das auch akzeptal...für's Üben ;)\n",
    "\n",
    "prog_bin = [\n",
    "    ['z_start','0','0','z_start','R'], # Nach rechts laufen ohne\n",
    "    ['z_start','1','1','z_start','R'], # etwas zt verändern\n",
    "    ['z_start','_','_','z_1','L'], # und wieder eins nach links\n",
    "    ['z_1','0','1','z_ende','-'],  # Fertig, falls Zeichen unter Lesekopf 0\n",
    "    ['z_1','1','0','z_1','L'],     # 0 schreiben, falls 1 gefunden, Übertrag\n",
    "    ['z_1','_','1','z_ende','-']   # Fertig, vorne eine 1 schreiben    \n",
    "]\n",
    "\n",
    "\n",
    "def run(name,prog,eingabe,debug=True):\n",
    "    turing_maschine = Turing(prog,eingabe)\n",
    "\n",
    "    print(\"Turingmaschine \",name,\" ist im Startzustand z_start\")\n",
    "    print(\"Die Eingabe (mit Eingabezeiger-Position):\")\n",
    "    print(\"    --> \", turing_maschine.show_input())\n",
    "    print(\"    --> \", turing_maschine.show_input_pointer())\n",
    "\n",
    "    turing_maschine.step(debug)\n",
    "    print(\"\\n\") # Leerzeile ausgeben)\n",
    "    # input()  # wieder einkommentieren, wenn Sie es nicht im Notebook, sondern direkt in Python ausführen\n",
    "    # z.B. auf https://repl.it/python3\n",
    "    \n",
    "\n",
    "# Jetzt führen wir mal 5 Turingmaschinen aus...\n",
    "\n",
    "run(\"Invertiere\",prog_inv,['1','0','1','1','0'])\n",
    "run(\"Addiere_1\",prog_bin,['1','0','1','1','0'])\n",
    "run(\"Addiere_1\",prog_bin,['1','1','1','1','1'])  # Debug-Ausgabe ausschalten\n",
    "run(\"Addiere_1\",prog_bin,['_'])\n",
    "run(\"Addiere_1\",prog_bin,['1','0','2','0'])\n",
    "\n",
    "# Jetzt können Sie selbst eine Turingmaschine bauen - versuchen Sie sich doch \n",
    "# an der Addition von zwei Binärzahlen, s. oben!\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Hier ist Platz für ihre eigenen Experimente!\n",
    "\n",
    "# Sie können eine Codezelle mit z.B. Shift-Enter ausführen, vorausgesetzt, Sie haben ihren Notebook-Server\n",
    "# ans Laufen gebracht - installieren Sie dazu Anaconda für Python 3 und starten Sie dann den \n",
    "# Anaconde-Navigator und dort wählen Sie \"Jupyter Notebook\".\n",
    "\n",
    "# Sie können das Python3-Programm von oben aber auch einfach nach repl.it kopieren und dort ausführen. \n",
    "# https://repl.it/python3 - wenn Sie sich da einen Account zulegen, können sie ihre Arbeit sogar\n",
    "# dort speichern und ihren Kommilitonen (und uns) zugänglich machen!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}