Turingmaschine

Aus AnthroWiki
(Weitergeleitet von Turing-Vollständigkeit)
Ein physisch realisiertes Modell einer Turingmaschine

Die Turingmaschine ist ein 1936[1] von dem britischen Mathematiker und Logiker Alan Turing (1912-1954) eingeführtes Berechenbarkeitsmodell, das die Arbeitsweise eines Computers mathematisch exakt beschreibt und damit eine wesentliche Grundlage der theoretischen Informatik ist. Es handelt sich dabei also um ein Gedankenmodell und nicht um ein physisch realisiertes Gerät. Turing analysierte dazu die menschlichen Gedankenprozesse beim Zahlenrechnen und bildete sie in seinem Modell nach, indem er die mathematischen Begriffe „Berechenbarkeit“ und „Algorithmus“ (Rechenvorschrift) streng formalisierte.

Schematischer Aufbau einer Turingmaschine

Schematischer Aufbau einer Ein-Band-Turingmaschine

Eine einfache Turingmaschine repräsentiert einen bestimmten Algorithmus bzw. ein Programm. Sie verfügt über ein endloses, in quadratische Felder eingeteiltes Band, das als Datenspeicher mit unbeschränkter Kapazität dient. Die Felder können mit Zeichen (inklusive Leerzeichen) aus einem definierten Zeichensatz - im einfachsten Fall 0 und 1 - beschrieben werden. Das Band wird durch einen beweglichen Lese- und Schreibkopf gelesen bzw. beschrieben, wobei das Band programmgesteuert vorwärts und rückwärts bewegt und das jeweilige Zeichen verändert werden kann. Die Maschine startet bei dem ersten eingegebenen Zeichen und stoppt, wenn für den aktuellen Zustand und das gerade gelesene Zeichen keine weitere Aktion definiert ist. Die Frage, ob der Algorithmus nach einer endlichen Zahl von Schritten zum Ende kommt, wird als Halteproblem bezeichnet. Für einfache Algorithmen kann diese Frage meist leicht beantwortet werden. Turing hat aber mittels seiner universellen Turingmaschine (siehe unten) nachgewiesen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantworten könnte. Das Halteproblem ist daher algorithmisch nicht entscheidbar. Erkenntnistheoretisch folgt daraus, dass grundsätzlich nicht jedes Problem formal logisch lösbar ist, selbst wenn alle dafür relevanten Fakten bekannt sind. Das trifft sich mit dem bereits 1931 von Kurt Gödel (1906-1978) formulierten Gödelschen Unvollständigkeitssatz.[2]

In seinem 1948 veröffentlichten Bericht Intelligent Machinery beschrieb Turing seine „Logischen Berechnungsmaschinen“ (Logical Computing Machines, kurz: LCM) wie folgt:

„In Turing (1937) wurde ein bestimmter Typ einer diskreten Maschine beschrieben. Sie hatte eine unendliche Speicherkapazität in Form eines unendlichen Bandes, das in Quadrate unterteilt ist, auf die jeweils ein Symbol gedruckt werden kann. Zu jedem Zeitpunkt befindet sich ein Symbol in der Maschine; es wird das gescannte Symbol genannt. Die Maschine kann das gescannte Symbol ändern und sein Verhalten wird teilweise durch dieses Symbol beschrieben, aber die Symbole an anderer Stelle auf dem Band haben keinen Einfluss auf das Verhalten der Maschine. Das Band kann jedoch durch die Maschine hin- und herbewegt werden, wobei dies eine der elementaren Operationen der Maschine ist. Jedes Symbol auf dem Band kann daher irgendwann einen Durchgang haben.

Diese Maschinen werden hier 'Logical Computing Machines' genannt. Sie sind vor allem von Interesse wenn wir überlegen wollen, wozu eine Maschine prinzipiell ausgelegt sein könnte, wenn wir bereit sind um sowohl unbegrenzte Zeit als auch unbegrenzte Speicherkapazität zu ermöglichen.“

Alan Turing: Intelligent Machinery (1948)[3]

Formale Definition

Formal lässt sich eine Turingmaschine als 7-Tupel darstellen:

  • ist die endliche nichtleere Zustandsmenge
  • ist das endliche nichtleere Eingabealphabet
  • ist das endliche nichtleere Bandalphabet, wobei gilt:
  • ist die (partielle) Übergangsfunktion bzw. -relation
  • ist der Anfangszustand
  • ist das leere Feld (Blank)
  • die Menge der akzeptierenden Endzustände

Universelle Turingmaschine

Bei einer einfachen Turingmaschine (LCM), wie sie oben beschrieben wurde, ist das Programm fester unveränderlicher Bestandteil der Maschine selbst. Eine universelle Turingmaschine ist nun eine solche, die jede beliebige einfache Turingmaschine dadurch simulieren kann, dass das Programm letzterer als Zeichenkette selbst einen Teil der auf dem Band gespeicherten Eingabe bildet. Im Prinzip funktionieren die meisten heutigen Computer nach diesem Prinzip.

„Es ist möglich, LCMs sehr standardisiert zu beschreiben und die Beschreibung in eine Form zu bringen, die von einer speziellen Maschine "verstanden" (d.h. angewendet) werden kann. Insbesondere ist es möglich, eine "Universalmaschine", die eine LCM ist, so zu konstruieren, dass wenn die Standardbeschreibung einiger anderer LCMs von außen auf das ansonsten leere Band eingegeben wird und die (universelle) Maschine dann in Gang gesetzt wird, sie die Operationen der jeweiligen Maschine ausführt, deren Beschreibung ihr gegeben wurde. Für Details wird der Leser auf Turing (1937) verwiesen.

Die Bedeutung der Universalmaschine ist klar: Wir benötigen nicht unendlich viele verschiedene Maschinen, die verschiedene Aufgaben erfüllen. Eine einzige genügt. Das technische Problem der Herstellung verschiedener Maschinen für verschiedene Aufgaben wird durch die Büroarbeit der 'Programmierung' der universellen Maschine ersetzt, die diese Aufgaben zu erledigt.

In der Praxis zeigt sich, dass LCMs alles tun können, was man als "Faustregel" als "rein mechanisch" bezeichnen könnte. Dies ist hinreichend belegt, so dass nun unter den Logikern vereinbart ist, dass "mit Hilfe einer LCM berechenbar" die korrekte und genaue Wiedergabe dieser Phrasen ist.“

Alan Turing: Intelligent Machinery (1948)[4])

Deterministische und nichtdeterministische Turingmaschinen

Eine deterministische Turingmaschine (DTM) hat eine Übergangsfunktion, die das Zeichen, das auf das Band geschrieben werden soll genau festlegt, ebenso die Richtung, in die der Lese- und Schreibkopf weiterbewegt werden soll und der Zustand in den gewechselt wird.

Eine nichtdeterministische Turingmaschine (NTM) verfügt hingegen über eine Übergangsrelation, die die Übergangsfunktion nicht eindeutig festlegt, sondern dafür mehrere Möglichkeiten anbietet. Dieses Modell ist insbesondere für die Komplexitätstheorie bedeutsam. Es gibt hier keinen eindeutigen Ablauf für jede Eingabe, sondern es sind verschiedene Abläufe möglich. Diese werden entweder alle parallel ausgeführt oder zufällig ausgewählt. Im letzteren Fall handelt es sich um eine probabilistische Turingmaschine (PTM). Sie verfügt bei jedem Rechenschritt über zwei Übergangsfunktionen, von denen jeweils eine zufällig ausgewählt wird. Ein zweiter Durchlauf der Maschine mit den selben Eingabedaten kann daher zu einem ganz anderen Ergebnis führen.

Turing-Vollständigkeit

Als Turing-vollständig wird ein logisches System bzw. eine Programmiersprache gemäß der Berechenbarkeitstheorie bezeichnet, wenn mit ihrer Hilfe sämtliche Funktionen berechnet werden können, die auch eine universelle Turingmaschine berechnen kann. Physikalisch lässt sich ein solches System nicht realisieren, da es über einen unbegrenzten Speicherplatz verfügen müsste. Dennoch werden alle gängige Programmiersprachen und Computer, die universell wären, wenn sie einen unbegrenzten Speicher besäßen, als Turing-vollständig bezeichnet.

Church-Turing-These

Eine mathematische Funktion wird als Turing-berechenbar oder kurz als berechenbar bezeichnet, wenn sie mit einer Turingmaschine berechnet werden kann. Gemäß der Church-Turing-These stimmt die Klasse der Turing-berechenbaren mit der Klasse der intuitiv berechenbaren Funktionen überein[5]. Eine Funktion, die mittels einer Turingmaschine nicht berechnet werden kann, gilt damit erwiesenermaßen als nicht berechenbar. Tatsächlich stellte Turing fest, dass viele Funktionen, die sich der Mensch ausdenken kann, grundsätzlich nicht berechenbar.

Siehe auch

Einzelnachweise

  1.  Alan M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. 42, 1937, S. 230–265, doi:10.1112/plms/s2-42.1.230 (pdf).
  2. Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. In: Monatshefte für Mathematik und Physik. 38, 1931, S. 173–198, doi:10.1007/BF01700692. Zentralblatt MATH.
  3. „In Turing (1937) a certain type of discrete machine was described. lt had an infinite memory capacity obtained in the form of an infinite tape marked out into squares on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behaviour is in part described by that symbol, but the symbols on the tape elsewhere do not affect the behaviour of the machine. However the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.
    These machines will here be called ‘Logical Computing Machines’. They are chiefly of interest when we wish to consider what a machine could in principle be designed to do, when we are willing to allow it both unlimited time and unlimited storage capacity.“ (Alan M. Turing: Intelligent Machinery, 1948, The Turing Archive, S. 3f.)
  4. „It is possible to describe LCMs in a very standard way, and to put the description into a form which can be ‘understood’ (i.e., applied by) a special machine. In particular it is possible to design a ‘universal machine’ which is an LCM such that if the standard description of some other LCM is imposed on the otherwise blank tape from outside, and the (universal) machine then set going it will carry out the operations of the particular machine whose description it was given. For details the reader must refer to Turing (1937).
    The importance of the universal machine is clear.We do not need to have an infinity of different machines doing different jobs. A single one will suffice. The engineering problem of producing various machines for various jobs is replaced by the office work of ‘programming’ the universal machine to do these jobs.
    It is found in practice that LCMs can do anything that could be described as ‘rule of thumb’ or ‘purely mechanical’. This is sufficiently well established that it is now agreed amongst logicians that ‘calculable by means of an LCM’ is the correct accurate rendering of such phrases.“ (Alan M. Turing: Intelligent Machinery, 1948, The Turing Archive, S. 3f.
  5. Benannt nach Alan Turing und dem US-amerikanischen Mathematiker, Logiker und Philosophen Alonzo Church (1903-1995), der einer der Mitbegründer der theoretischen Informatik war. Die Church-Turing-These ist zwar nicht formal beweisbar, da sich der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisieren lässt, wird aber allgemein als gültig angesehen.