Die erste Turingmaschine

Weiß jemand, wie effizient die erste Turing-Maschine war, die Alan Turing hergestellt hat? Ich meine, wie viele Züge hat es pro Sekunde oder so gemacht ... Ich bin nur neugierig. Ich konnte auch keine Informationen darüber im Web finden.

"Turingmaschinen" (oder "a-Maschinen") sind ein mathematisches Konzept, keine tatsächlichen physischen Geräte. Turing hat sie entwickelt, um mathematische Beweise über Computer mit der folgenden Logik zu schreiben:

• Das Schreiben von Proofs über physische Drähte und Schalter ist äußerst schwierig.
• Das Schreiben von Proofs über Turing-Maschinen ist (relativ) einfach.
• Alles, was physische Drähte und Schalter können, können Sie eine Turing-Maschine bauen, um (*) (**) zu tun.

Aber Turing hat nie eine Maschine gebaut, die Symbole auf ein Papierband schrieb. Andere Leute haben, aber nur als Demonstration: Hier ist eine, die Sie zum Beispiel aus einer Visitenkarte machen können .

Warum hat er nie eine physische Turingmaschine gebaut? Einfach gesagt, wäre es einfach nicht so nützlich. Die Sache ist, dass niemand jemals ein Rechenmodell entwickelt hat, das stärker ist als eine Turing-Maschine (da es Dinge berechnen kann, die eine Turing-Maschine nicht kann). Und es ist erwiesen, dass mehrere andere Rechenmodelle, wie der Lambda-Kalkül oder die Programmiersprache Python, "Turing-complete" sind: Sie können alles, was eine Turing-Maschine kann.

Für alles außer einem mathematischen Beweis ist es im Allgemeinen viel nützlicher, eines dieser anderen Modelle zu verwenden. Dann können Sie die Turing-Maschinen in Ihren Proofs ohne Verlust der Allgemeinheit verwenden.

(*) Insbesondere jede Berechnung : Eine Turing-Maschine kann beispielsweise keine Glühbirne einschalten, aber Glühbirnen sind vom Standpunkt der Berechnungstheorie aus nicht sehr interessant.

(**) Wie in den Kommentaren ausgeführt wurde, war Turings Hauptdefinition von "Computer" ein Mensch, der einem Algorithmus folgte. Er vermutete, dass es keine Berechnung gibt, die ein Mensch ausführen kann, die eine Turing-Maschine nicht ausführen kann - aber niemand hat dies beweisen können, auch weil es unglaublich schwierig ist, genau zu definieren, was ein menschlicher Verstand tun kann. Schauen Sie sich die Church-Turing-These an, wenn Sie interessiert sind.

Turing hat nie eine physische Turing-Maschine gebaut. Bei Turing-Maschinen ging es nicht darum, ein praktischer physischer Computer zu sein, sondern zu formalisieren, was berechnet werden kann, und tatsächlich zu formalisieren, was "Berechnung" überhaupt bedeutet.

Lassen Sie mich ernsthaften Spaß mitbringen, obwohl dies möglicherweise nicht die gewünschte Antwort ist.

Anspruch 1 : Viele Turing-Maschinen wurden von Alan Turing und vielen anderen gebaut.

Beweis. Alan Turing zeigte auf einen unbeweglichen Bolzen in einer Bombe und sagte mit seiner üblichen scharfen Einsicht und Einfachheit: "Schauen Sie, eine Turing-Maschine, die bei jeder Eingabe anhält."

Moral : Es gibt viele Arten von Turingmaschinen. Viele von ihnen sind sehr einfach. Aber sie sind (funktional) Turingmaschinen.

Anspruch 2 : Es ist unentscheidbar, ob eine Maschine unbegrenzten Speicher hat.

Beweis. Ich habe eine Rechenmaschine, für die es eine Sekunde dauert, um jedes zusätzliche Speicherbit zu demonstrieren. Ich möchte Sie davon überzeugen, dass es kein unbegrenztes Gedächtnis gibt. Als vorsichtiger Positivist bestehen Sie jedoch darauf, dass niemand ablehnen kann, dass das Gedächtnis in naher Zukunft oder sogar für immer unbegrenzt ist.

Moral : Seien Sie vorsichtig, wenn wir über Objekte sprechen, die sich bei Bedarf ausdehnen.

Dies ist ein perfekter Ort und eine perfekte Zeit, um sich auf das eigentliche Papier zu beziehen, in dem die Turing-Maschine zuerst beschrieben wird. Ein Link ist hier:

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Natürlich ist er bescheidener, deshalb nennt er es die "automatische Maschine". Es gibt keine wirkliche Maschine, nur ein Tier der Fantasie.

Soweit wir wissen, hat Turing noch nie versucht, die "automatische Maschine" zu bauen. Er war jedoch äußerst einflussreich bei der Herstellung einer Reihe anderer Maschinen. Das bekannteste Beispiel ist die Bombe aus dem Zweiten Weltkrieg, mit der Nazi-Deutschland-Reißverschlüsse gebrochen wurden.

Leider wurde die breite Öffentlichkeit erst lange nach seinem Tod auf seine Leistungen aufmerksam gemacht. (Er soll sich umgebracht haben, nachdem er als verurteilter Homosexueller brutal einer chemischen Sterilisation unterzogen worden war).

Das TM existiert nur auf Papier. Es ist ein theoretisches Rechenmodell. Es kann eigentlich nicht gebaut werden (weil das Band unendlich lang ist).

Die Antwort lautet also: Nein, Turing hat im wirklichen Leben nie ein TM gebaut, weil er es nicht kann.

Bitte argumentieren Sie nicht weiter: "Wir können eine Turing-Maschine bauen, nur dass sie kein unendliches Band hat, denn per Definition hat ein TM ein unendlich langes Band. Wenn es kein unendlich langes Band hat, dann ist es kein." Turingmaschine. So einfach ist das.

Ich bin mir völlig bewusst, dass Leute "TMs mit endlichen Bändern" erstellt haben, und ich bezweifle auch nicht die Nützlichkeit davon (dh begrenzte Automaten): Tatsächlich können wir bei einem ausreichend langen Band im Grunde alle praktisch interessanten Dinge berechnen (die Turing sind) berechenbar). Aber für jede natürliche Zahl$n$wird es ein TM geben, das notwendigerweise ein Band mit einer Länge erfordern würde $n+1$zu simulieren, so gibt es nie ein "groß genug" Band. (Überlegen Sie warum.)

Wenn Sie einen Schritt zurücktreten, gibt es leicht TMs, die wir nicht mit endlichen Ressourcen erstellen oder simulieren können. Nehmen Sie das TM, das im ersten Schritt ein * schreibt, nach rechts geht und im zweiten Schritt zwei * schreibt usw. Dieses TM kann ohne unendlich viel Speicher nicht erstellt oder sogar simuliert werden.

Hier ist ein Video mit einer echten Turing-Maschine. Es ist ganz nett und hat mir geholfen, es nicht mehr nur als mathematisches Modell zu betrachten:

https://www.youtube.com/watch?v=E3keLeMwfHY