Turingmaschine

Aus AnthroWiki
Version vom 7. August 2018, 09:56 Uhr von imported>Odyssee
Schematischer Aufbau einer Ein-Band-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. 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.

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)[2])

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[3]. 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. „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.
  3. Benannt nach Alan Turing und dem US-amerikanischen Mathematiker, Logiker und Philosophen [[Wikipedia: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.