Home >Documents >Facharbeit - .St¤dtisches Labenwolf-Gymnasium N¼rnberg Kollegstufe 2001/2003 Schuljahr...

Facharbeit - .St¤dtisches Labenwolf-Gymnasium N¼rnberg Kollegstufe 2001/2003 Schuljahr...

Date post:17-Sep-2018
Category:
View:215 times
Download:0 times
Share this document with a friend
Transcript:
  • Stdtisches Labenwolf-Gymnasium Nrnberg

    Kollegstufe 2001/2003 Schuljahr 2002/2003

    Facharbeit aus dem Fach Mathematik

    Thema: Die Turingmaschine Verfasser: Stefan Thomas Schorsch Kursleiter: Hans Gaab Abgabetermin: 3.Februrar 2003 Wertung: Erzielte Punktzahl (einfache Wertung): ....... in Worten: ............................................................... ................................................................................................................................... Kursleiter Hans Gaab

  • 1. Einleitung Seite 03 2. Das Prinzip Seite 04

    2.1. Das Prinzip allgemein Seite 04 2.1.1. Turingmaschine als Blackbox Seite 04 2.1.2. Das Turingband Seite 05 2.1.3. Der Lese- bzw. Schreibkopf Seite 05 2.2. Mglicher mechanischer Aufbau Seite 05 2.3. Mathematische Definition Seite 06

    3. Beispielanwendungen Seite 07 3.1. Schreibweise fr Turingprogramme Seite 07 3.2. Addition unrer Zahlen Seite 10 3.3. Verdopplung einer unren Zahl Seite 13 3.4. Multiplikationsprogramm Seite 16

    4. Theorie zur Turingmaschine Seite 21 4.1. Mehrbndige Turingmaschinen Seite 21 4.2. Gre des Bandalphabetes Seite 21 4.3. Berechenbarkeitstheorie Seite 22 4.4. Formale Bedeutung der Turingmaschine Seite 22 4.4.1. Turingmaschine als Generator Seite 22 4.4.2. Turingmaschine als Akzeptor Seite 22

    5. Das Busy-Beaver-Problem Seite 23

    6. Turingsimulatoren Seite 25 6.1. Freeware-Turing-Maschine Seite 25 6.2. Facharbeitsturingmaschine Seite 25 6.3. Visual Turing Seite 26

    7. Schluss und Quellenangabe Seite 27 7.1. Bilder(Quellennachweis) Seite 27 7.2. Sonstige Quellen Seite 28 7.3. Abschlusserklrung Seite 30

  • - Seite 3 -

    1. Einleitung Alan Mathison Turing ist einer der bedeutendsten Mathematiker des 20. Jahrhunderts, berhmt fr seine Grundlagenarbeit auf dem Gebiet der Mathematik und Informatik. Zu Lebzeiten genoss er kein hohes Ansehen und beendete sein Leben schlielich durch Selbstmord; erst nach seinem Tod erkannte man das volle Ausma seiner Leistungen und die Auswirkungen seiner Arbeiten.

    Geboren am 23. Juni 1912 in Paddington (London), als zweites Kind von Julius Mathison and Ethel Sara Turing, ging vom Elternhaus zunchst wenig Interesse an Forschungsarbeiten aus; einzig sein Onkel, der irische Physiker George Johnstone Stoney (1826-1911), knnte einen Einfluss auf ihn gehabt haben. Turings Kindheit verlief in ruhigen Bahnen. Obwohl er zu diesem Zeitpunkt in keiner Weise gefrdert wurde, erwachte sein Interesse an der Wissenschaft und uerte sich schon in einigen simplen Chemieversuchen. Er besuchte die "Sherborne School, deren Direktor folgenden Satz gesagt haben soll: "If he is to be solely a Scientific Specialist, he is wasting his time at a Public School (Der Schuldirektor der Sherborne School ber Alan Turing, gefunden auf Hodges, Andrew Alan Turing: a short biography, Internetseite http://www.truing.org.uk/bio/part1.html von 1995,

    aufgerufen am 30.12.2002) Wenn er ausschlielich ein Wissenschaftsexperte werden wird, verschwendet er seine Zeit an ffentlichen Schulen. Damit lag der Schulleiter erstaunlich nahe an der Zukunft.

    Abbildung 1

    Von 1931 an war Turing Student am Kings College in Cambridge, wo sich ihm mehr denkerische Freiheiten erffneten. Hier arbeitete er erfolgreich an verschiedenen Projekten und gewann sogar einige Preise, bis er sich entschied, eine andere Richtung zu beschreiten. Die damals aktuelle Diskussion ber nicht beweisbare Axiome und besonders das vom deutschen Mathematiker David Hilbert gestellte Entscheidungsproblem vereinnahmten ihn: "Could there exist, at least in principle, a definite method or process by which it could be decided whether any given mathematical assertion was provable? (Das Entscheidungsproblem, gefunden auf Hodges, Andrew Alan Turing: a short biography, Internetseite http://www.truing.org.uk/bio/part2.html von 1995, aufgerufen am 30.12.2002); Existiert, zumindest im Prinzip, eine sichere Methode oder ein sicheres Verfahren, durch welches man entscheiden knnte, ob ein beliebiger mathematischer Ausdruck beweisbar wre?. Diese Fragestellung fhrte schlielich zur Turingmaschine: Turing analysierte den Denkprozess eines Menschen und versuchte ihn derart zu vereinfachen, dass eine theoretisch physikalisch konstruierbare Maschine den Denkprozess nachvollziehen knnte. Der Erfinder konnte ebenfalls beweisen, dass diese Maschine alles berechnen konnte, was in der Mathematik fortan als bestimmter Algorithmus definiert war. Damit lie sich nun auch Hilberts Fragestellung sehr schnell mit nein beantworten: eine solche Methode kann nicht existieren. Mit dieser Turingmaschine beschftigt sich nun die Facharbeit.

    http://www.truing.org.uk/bio/part1.htmlhttp://www.truing.org.uk/bio/part2.html

  • - Seite 4 -

    Natrlich war dies nicht die letzte Arbeit von Alan Turing: von groer Bedeutung waren noch seine Arbeiten zur Entschlsselung der deutschen Engima-Verschlsselungsmaschine und zu den Themen neuronale Netze und knstliche Intelligenz. Spter erhielt er unter anderem einen Posten an der Universitt von Manchester, wo er fr die Elektronikentwicklung der britischen Atombombe eingesetzt wurde. Es folgten einige nicht weniger bedeutsame Werke, auf die jedoch nicht nher eingegangen werden soll. Im weiteren Verlauf wurde Turing vom Glck verlassen. In der damalig vorherrschenden Zeitstrmung, bedingt durch den Kalten Krieg und den amerikanischen Einfluss, verlor Turing nicht nur seine Sicherheitsfreigaben der britischen Regierung, sondern sollte sogar fr seine homosexuellen Neigungen eingesperrt werden. Dies alles fhrte vermutlich am 7. Juni 1954 zu seinem durch Zyanid herbeigefhrten Selbstmord. Erst Jahre nach seinem Tod erhielten seine Arbeiten die Anerkennung, die ihm ungerechterweise zu Lebzeiten verwehrt blieb. Auch heute, mehr als 60 Jahre nach der Erfindung der Turingmaschine, ist sie noch Lehrstoff der meisten Informatikstudiengnge. Es existiert bis dato kein besseres Modell, um mit der Berechenbarkeitstheorie zu arbeiten. Was ist also eigentlich eine Turingmaschine? 2. Das Prinzip der Turingmaschine Zunchst ist es wichtig, hervorzuheben, dass eine Turingmaschine keinesfalls mit einem heute gebruchlichen PC vergleichbar ist, sondern vielmehr ein Gedankenmodell bzw. die Konkretisierung eines solchen darstellt. Darber hinaus muss auch sorgfltig zwischen Hard- und Software unterschieden werden. Ein mglicher mechanischer Aufbau wird in Kapitel 2.2 vorgestellt. Hier zunchst eine allgemeine Einfhrung in die Turingmaschine. 2.1. Das Prinzip allgemein Eine Turingmaschine besteht stets aus den gleichen elementaren Bestandteilen:

    - Ein Steuermechanismus (Kapitel 2.1.1.) - Das Turingband (Kapitel 2.1.2.) - Der Lese- und Schreibkopf (Kapitel 2.1.3.)

    2.1.1. Turingmaschine als Blackbox Der Steuermechanismus der Turingmaschine kann auch als Blackbox verstanden werden. Es ist fr den Anwender nicht wesentlich, wie die Turingmaschine ihre Berechnungen intern durchfhrt, er muss nur wissen, welche Eingaben mglich, und welche Ausgaben zu erwarten sind (= Blackboxprinzip). Insofern hat der mechanische innere Aufbau auch keine groe Bedeutung. Der Steuermechanismus muss lediglich dazu in der Lage sein, die Eingabe aufzunehmen und entsprechend darauf einen Befehl

  • - Seite 5 -

    fr die Ausgabe (in Form des zu schreibenden Symbols und der Bewegungsrichtung des Bandes) abzusetzen. Darber hinaus muss in dieser Blackbox auch noch festgelegt sein, wie die Turingmaschine auf bestimmte Eingaben reagieren soll (im Normalfall gespeichert in sogenannten Registern). 2.1.2. Das Turingband Das sog. Turingband ist der Speicherort der Turingmaschine. Das Band ist in einzelne Zellen eingeteilt, die jeweils ein Zeichen aufnehmen und speichern knnen. Fr die Berechenbarkeitstheorie relevant ist die Tatsache, dass dieses Band per Definition unendlich lang sein muss (um eine Funktion nicht einfach aufgrund mangelnder Speicherkapazitt nicht berechnen zu knnen). Praktisch lsst sich ein unendlich langes Band natrlich mit keinem bisher bekannten Verfahren simulieren. Das Band lsst sich sowohl nach links als auch nach rechts bewegen, so dass eine entsprechende Lesevorrichtung jedes Bandfeld erfassen bzw. beschreiben kann. 2.1.3. Der Lese- bzw. Schreibkopf Der Lese-/Schreibkopf ist das Datenerfassungs- und Ausgabeelement der Turingmaschine. Er kann ein Zeichen vom Turingband einlesen, es an den Steuerungsmechanismus weiterleiten. Dieser verarbeitet das gesendete Symbol und gibt an den Schreibkopf die Anweisung fr das neu in die gleiche Zelle zu schreibende Zeichen. Darber hinaus erhlt er die Anweisung, in welche Richtung das Turingband nun zu bewegen ist. 2.2. Mglicher mechanischer Aufbau Wie bereits erwhnt, ist die Turingmaschine nicht dafr prdestiniert, real nachgebaut zu werden; ihre Leistung und Benutzerfreundlichkeit wrden keinen gebruchlichen Standards entsprechen. Trotzdem ist es sehr viel anschaulicher und nachvollziehbarer, wenn man ein mgliches physisches Abbild betrachtet:

    Abbildung 2

  • - Seite 6 -

    Deutlich erkennbar ist das Turingband. Der Doppelpfeil deutet an, dass das Band sowohl nach links als auch nach rechts verschoben werden kann. Der Lese-/Schreibkopf sitzt ber dem Band und empfngt/bermittelt die Informationen aus der Blackbox. Diese kann entweder gestartet oder zurckgesetzt werden. Ein Eingriff in eine laufende Berechnung ist also nicht mglich. Softwareseitige Simulationen sind in Kapitel 6 aufgelistet.

    2.3. Mathematische Definition Um der Tatsache gerecht zu werden, ein mathematisches Denkmodell dar

Click here to load reader

Embed Size (px)
Recommended