Turingmaschine: Unterschied zwischen den Versionen

Aus AnthroWiki
imported>Odyssee
Keine Bearbeitungszusammenfassung
imported>Odyssee
Keine Bearbeitungszusammenfassung
Zeile 7: Zeile 7:
   |Seiten=230–265
   |Seiten=230–265
   |DOI=10.1112/plms/s2-42.1.230
   |DOI=10.1112/plms/s2-42.1.230
   |Online=[https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf pdf]}}</ref> von dem britischen [[Mathematiker]] und [[Logik]]er [[Alan Turing]] (1912-1954) eingeführtes [[Berechenbarkeit]]smodell, das Arbeitsweise eines [[Computer]]s mathematisch exakt beschreibt und damit eine wesentliche Grundlage der [[Theoretische Informatik|theoretischen Informatik]] bildet.  
   |Online=[https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf pdf]}}</ref> von dem britischen [[Mathematiker]] und [[Logik]]er [[Alan Turing]] (1912-1954) eingeführtes [[Berechenbarkeit]]smodell, das die Arbeitsweise eines [[Computer]]s mathematisch exakt beschreibt und damit eine wesentliche Grundlage der [[Theoretische Informatik|theoretischen Informatik]] ist. Turing analysierte dazu die menschlichen Gedankenprozesse beim [[Rechnen|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 seinem 1948 veröffentlichten Bericht ''Intelligent Machinery'' beschrieb Turing seine „''Logischen Berechnungsmaschinen“ (''Logical Computing Machines'', kurz: LCM) wie folgt:

Version vom 7. August 2018, 09:01 Uhr

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

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.