Turing's Tape

1936 · Universal Machine · Werk 510 von 1.871

Turing's Tape, 1936, Universal Machine

A page of a mathematical journal of 1936, typeset paragraphs reading as grey texture, a printed table of machine configurations ruled into columns in the middle of the page, cream paper laid flat on a grey studio table, even flat light from directly above.

Wofür es benutzt wurde
Alan Turings Aufsatz "On Computable Numbers, with an Application to the Entscheidungsproblem" erschien in den Proceedings of the London Mathematical Society, zweite Reihe, Band 42, Seiten 230 bis 265. Der Kopf des Drucks nennt zwei Daten verschiedener Art: eingegangen am 28. Mai 1936, vorgetragen am 12. November 1936. Am Schluss steht als Anschrift das Graduate College in Princeton. Die Aufgabe nennt er selbst: es werde gezeigt, dass das Hilbertsche Entscheidungsproblem keine Lösung haben kann. Das Band ist dabei Hilfsmittel, nicht Ziel. Turing vergleicht den Menschen beim Rechnen mit einer Maschine, die nur endlich viele Zustände hat, die er m-Konfigurationen nennt. Durch sie läuft ein Band, das Gegenstück zum Papier, in Felder geteilt, jedes für ein Zeichen. Nur ein Feld ist jeweils in der Maschine, und nur dessen Zeichen ist ihr unmittelbar bewusst.
Was daran neu war
Das Kernstück des Aufsatzes ist die universelle Maschine: es sei möglich, eine einzige Maschine zu erfinden, mit der jede berechenbare Folge berechnet werden kann, wenn man ihr auf dem Band die Beschreibung einer anderen Maschine vorlegt. Mit dem Ergebnis zum Entscheidungsproblem war Turing nicht allein, und er sagt es auf der zweiten Seite selbst: Alonzo Church habe kürzlich den Begriff der effective calculability eingeführt, der mit seiner Berechenbarkeit gleichwertig, aber ganz anders definiert sei, und komme zu ähnlichen Schlüssen über das Entscheidungsproblem. Turing hängte darum einen Anhang vom 28. August 1936 an, der die Gleichwertigkeit umreißt. Church schrieb 1937 in seiner Besprechung, sein eigenes Ergebnis sei dem Turings vorausgegangen, dessen Arbeit aber unabhängig entstanden und beim Erscheinen von Churchs Aufsatz schon nahezu fertig und mehreren Personen im Kern bekannt gewesen — und prägte dort den Namen "Turing machine".

Zum Weiterlesen