Turing-Maschine: Wie können wir über Computer sprechen, wenn es keine Computer gibt?

Im Oktober 1950 wurde ein Artikel mit dem Titel „Can Machines Think“ veröffentlicht. In diesem Artikel wird ein schrecklicher Test vorgeschlagen, bei dem der Tester und das Subjekt (eine reale Person und eine Maschine) voneinander getrennt werden und dem Subjekt über ein Kommunikationsgerät zufällige Fragen gestellt werden und die Tester erraten, ob es sich um die Person handelt, mit der sie sprechen Es handelte sich um eine reale Person oder eine Maschine.

Wenn die Maschine nach mehreren Tests jeden Teilnehmer dazu bringen kann, durchschnittlich mehr als 30 % Fehleinschätzungen zu machen, dann hat die Maschine den Test bestanden und wird als menschlich angesehen .

Zu diesem Zeitpunkt erkannten die Menschen zum ersten Mal, dass Roboter möglicherweise über menschliche Intelligenz verfügen. Dieser Test ist der Turing-Test, über den Millionen Science-Fiction-Enthusiasten sprechen. Dieser Artikel brachte dem Autor Alan Turing auch den Titel „Vater der Künstlichen Intelligenz“ ein.

Der Weg zur künstlichen Intelligenz oder der Ursprung der Geschichte der Computerentwicklung ist ein Artikel, den Turing im Alter von 24 Jahren veröffentlichte. In diesem Artikel definierte er „Berechenbarkeit“ streng mathematisch und schlug die Idee der berühmten „Turingmaschine“ vor. Die Turing-Maschine ist keine spezifische Maschine, sondern ein mentales Modell, das ein sehr einfaches, aber äußerst leistungsfähiges Rechengerät erstellen kann, mit dem sich alle erdenklichen berechenbaren Funktionen berechnen lassen.

Weil Turing die Turing-Maschine erfunden hat, springt von Zeit zu Zeit jemand heraus und behauptet, dass Turing tatsächlich „den Computer erfunden“ hat. Allerdings sind Turing-Maschinen nicht auf die gleiche Weise konstruiert wie echte Rechenmaschinen. Eine Turingmaschine ist nicht einmal ein abstraktes Modell einer Maschine. Es stellt sich heraus (wie Turings Bemerkungen belegen), dass eine Turing-Maschine ein Modell einer Person ist, die auf Papier auf einem Tisch schreibt. Warum hat Turing die Turing-Maschine erfunden und wohin wird uns die Turing-Maschine führen?

1 Turings Artikel „Über berechenbare Zahlen“

Der beste Weg, diese Fragen zu beantworten, habe ich gestellt legte das Lehrbuch beiseite und schlug die Zeitung auf. Um eine Zeitschrift aus dem Jahr 1936 auszuleihen, muss man heute keine Leihkarte ausfüllen oder eine Stunde warten, bis ein Bibliothekar sie aus der Bibliothek abholt. Alles, was wir brauchen, ist ein Glas Malt Whisky in der Hand und einen einfachen Zugriff auf Google zu Hause. Das von uns gesuchte Turing-Papier lautet wie folgt:

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

Es gibt einige Fehler im Papier, aber die Mängel werden nicht überwiegen. Wie Joel David Hamkins sagte, definierte Turing berechenbare reelle Zahlen als Zahlen mit berechenbaren Dezimalzahlen, was eigentlich nicht funktioniert, aber nicht schwer zu korrigieren ist.

Turing erläuterte die Absicht dieses Artikels im Titel: „Über berechenbare Zahlen und ihre Anwendung in „Entscheidungsproblemen““. ist eine effiziente Technik, um zu entscheiden, dass eine gegebene Logikformel erster Ordnung gültig ist, das heißt, dass sie für alle Interpretationen wahr ist. Erweitert seine Idee wie folgt: Eine Person, die reelle Zahlen berechnet, kann nur eine begrenzte Anzahl von Bedingungen erfüllen: q1, q2, ... qR ... Durch sie verläuft ein langes „Papierband“. Viele Teile nennen dieses Stück ein Quadrat, und jedes Quadrat kann ein „Symbol“ tragen ... Einige geschriebene Symbole bilden dezimale Ziffernfolgen der zu berechnenden reellen Zahlen, während andere Symbole nur grobe Notizen sind, die gelöscht werden können als „ Gedächtnishilfen.“ Mein Argument ist, dass die Arithmetik, auf einem Blatt Papier herumzurutschen, zu einem Symbol zu gleiten und etwas mit diesem Symbol zu tun, die gesamte Arithmetik umfasst, die für numerische Berechnungen erforderlich ist. #

……

„Berechenbare Zahlen“ sind einfach reelle Zahlen, deren Dezimaldarstellung nach meiner Definition mit begrenzten Mitteln berechnet werden kann, wenn der Dezimalausdruck einer Zahl sein kann Von einer Maschine geschrieben, ist die Zahl später berechenbar. Dies ist eine typische Mathematikarbeit, keine typische Ingenieurarbeit, in der die Leser eine Diskussion darüber sehen möchten, wie ein bestimmter Mechanismus implementiert wird Der Artikel Wie wir aus Turings Titel und Artikel ersehen können, ist Turings Hauptanliegen die Berechnung einer reellen Zahl auf unendliche Dezimalstellen.

Dieser Artikel enthält viele weitere wichtige Beiträge:

• Universelle Turing-Maschine und numerische Kodierung der Maschine Gedanken
• Das Halteproblem von Maschinen, die so codiert sind, und die Unentscheidbarkeit der Diagonalisierung

# 🎜🎜#Nach dem Schreiben dieses Artikels , Turing öffnete die Tür zum Bereich der theoretischen Informatik.

2 Universelle Turingmaschine

Wir sind nicht sicher, was Turing dazu veranlasst hat, die universelle Turingmaschine (UTM) zu produzieren ) Idee, aber sobald er darüber nachdachte, könnte er denken, dass die Existenz einer universellen Turing-Maschine offensichtlich sei. Denn der Zweck einer Turing-Maschine besteht darin, einen Angestellten zu simulieren, der an einem Schreibtisch arbeitet, und die Bedienung einer Turing-Maschine ist die gleiche wie die eines Angestellten – die Ausführung dieser oder jener Operation gemäß einer vorgegebenen Liste von Transformationsregeln, die auf der Maschine basieren Zustands- und Bandsymbole – es ist offensichtlich notwendig, dass eine Turing-Maschine solche Routineaufgaben ausführen kann. Turings Artikel war hinsichtlich der Details der Konstruktion etwas lückenhaft, aber niemand schien etwas dagegen zu haben.

Jetzt haben wir eine universelle Turingmaschine, die bis zum Äußersten entwickelt wurde. Vor Jahrzehnten schrieb Dr. Ken Moody an der Universität Cambridge einen universellen Minsky-Keygen: Link: http://www.igblan.free-online.co.uk/igblan/ca/minsky.html#🎜 🎜#

Auf diese Weise verfügt die Maschine über eine begrenzte Anzahl von Registern, von denen jedes eine beliebig große nicht negative ganze Zahl speichern kann. Es verfügt über ein endliches Programm, das aus drei verschiedenen Arten von getaggten Anweisungen besteht: 🎜🎜# und springe zum Tag

L, oder R

+→#🎜🎜 # L

• Register testen/dekrementieren R#🎜🎜 # und springe zum Tag L0/L1, oder # 🎜 🎜#L0↞R−→L
• 1#🎜🎜 # unterbrechen. Solche Maschinen sind einfacher zu programmieren als Turing-Maschinen, obwohl sie immer noch nicht wie echte Computer aussehen. Moody verwendet eine Standardbijektion zwischen N und N×N, um die ganzen Zahlen umzuwandeln. Die Liste ist in eine einzige ganze Zahl gepackt. Er schrieb eine kleine Bibliothek kleiner Registermaschinen, die Vorgänge wie Hochschieben und Herausnehmen aus dem Stapel ausführten, und erstellte ein Design, das an den Abruf-Ausführungszyklus eines echten Prozessors erinnerte. Der gesamte Prozess ist in den folgenden Folien zu sehen. Das Bild unten zeigt die Maschine selbst:
Das Bild unten zeigt den Gesamtaufbau der Maschine. (Der Autor beider Figuren ist Andrew Pitts, Professor für theoretische Informatik an der Universität Cambridge.) Der Aufbau dieser Maschine ist so einfach!
3

Das Stillstandsproblem

Das Stillstandsproblem ist offensichtlich unentscheidbar. Andernfalls sind viele mathematische Vermutungen schwer zu lösen, wie zum Beispiel der letzte Satz von Fermat: Schreiben Sie einfach ein Programm, um nach x, y, z, n>2 zu suchen, damit es beendet werden kann. Die Unentscheidbarkeit des Anhaltens muss jedoch rigoros zum Ausdruck gebracht und nachgewiesen werden.

Entgegen der landläufigen Meinung erörterte Turings Artikel nicht das Halteproblem, sondern eine mit dem Halteproblem verbundene Eigenschaft, die er „Zyklizität“ (Zirkularität) nannte. . Eine Turingmaschine ist zyklisch, wenn sie „nur eine begrenzte Anzahl der ersten Symbole schreibt“ (d. h. Nullen und Einsen). Ich denke, der Grund, warum Zyklizität wichtig ist, liegt darin, dass Turing besonders gern reelle Zahlen als unendliche Binärketten approximierte. Der Physiker Christopher Strachey behauptete 1965 in einem Brief an das Computer Journal, Turing habe ihm einen Beweis für die Unentscheidbarkeit des Halteproblems geliefert.

4 Turing und Maurice Wilkes

Im September 2009 interviewte David P. Anderson Maurice Wilkes über seine Ansichten zu Turing. Aber es ist genau das Gegenteil der Öffentlichkeit:

David P. Anderson: Welche Bedeutung hat Ihrer Meinung nach Turings Aufsatz von 1936 zum Entscheidungsproblem?

Maurice Wilkes: Ich denke, ein Ingenieur würde die Idee eines gespeicherten Programms als eine wichtige Theorie wie die Dreieinigkeit behandeln und sagen: „Das ist es.“ absolut erstklassig, und so soll es auch sein.“

Es gibt keinen praktischen Unterschied zwischen den Ideen in diesem Papier und dem, was ich gesagt habe. Er hatte Glück, dass dieser Artikel veröffentlicht wurde. Ich meine, Alonzo Church kam mit anderen Methoden zum gleichen Ergebnis.

Artikeladresse: https://cacm.acm.org/magazines/2009/9 /38898-an-interview-with-maurice-wilkes/fulltext

Es ist zu beachten, dass Maurice Wilkes zum Zeitpunkt des Interviews 96 Jahre alt war Jahre alt Ja, er selbst ist ein berühmter Computerpionier und der Vater von EDSAC (Electronic Delay Storage Automatic Calculator). In seiner seltsamen Antwort kann man seine Eifersucht auf Turings hohen Status erkennen. Die beiden verstehen sich offensichtlich nicht! Wir sehen auch die Verachtung von Maurice Wilkes für die Theorie: Obwohl von einem Computer mit gespeicherten Programmen erwartet wurde, die Maschine in Zahlen zu kodieren, war Turings Arbeit reine Mathematik und hatte keine technische Bedeutung. Turing interessierte sich sehr für tatsächliche Computertechnik, aber seine vielen Versuche, an echten Projekten teilzunehmen, scheiterten.

Und was halten Sie von diesen Kommentaren über Qiu Qi?

Als Turing forschte, konzentrierten sich viele Forscher auf die Idee der „effektiven Berechenbarkeit“. Hier empfehle ich den Lesern, „An Unsolvable Problem in Elementary Number Theory“ von Qiu Qi zu lesen (siehe Bild unten).

Papierlink: https://www.jstor.org/stable/2371045?origin =crossref

Ehrlich gesagt ist dieser Artikel schwer zu lesen, aber er kann uns in die Szene hineinführen. Dieser Artikel enthält eine Definition der λ-Kalküle, eine Definition einer rekursiven Funktion (im Sinne von Kleene/Gödel) und einige unbestreitbare Fragen zur Existenz und Äquivalenz von Paradigmen in der λ-Beurteilung. Church und Craney hatten die Äquivalenz zwischen durch Lambda definierbaren Funktionen und rekursiven Funktionen bewiesen, und während Turing in Princeton war, war auch die Äquivalenz zwischen durch Lambda definierbaren Funktionen und durch Turing berechenbaren Funktionen bewiesen worden, sodass wir die Church-Turing-These erhalten bezieht sich auf die Tatsache, dass effektiv berechenbare Funktionen genau diejenigen Funktionen in der mathematischen Äquivalenzklasse sind.

6 Ist die Qiu-Qi-Turing-These richtig?

Wie oft gesagt wird, können wir nicht beweisen, ob diese These richtig ist oder nicht, da „effektiv berechenbar“ kein präzises Konzept ist. Wir können uns die berechenbaren Turing-Funktionen als eine ziemlich umfassende Klasse vorstellen, da sie viele Funktionen enthält, die während der Lebensdauer des Universums nicht berechnet werden können. Mit Hilfe der Ackermann-Funktion können wir das Beispiel leicht erhalten.

Die moderne Form der Ackermann-Funktion lautet wie folgt: #Artikellink: https://lawrencecpaulson.github.io/2022/02/09 /Ackermann-example.html

if Wenn Sie f(n)=A(n,n) definieren, können Sie nicht erwarten, eine gerade Zahl zu berechnen f(4). g(n)=A(4,n) ist zwar eine primitive Rekursion, aber nahezu unmöglich zu berechnen.

Obwohl es bis in die 1930er Jahre keine digitalen Computer gab, war das Konzept der effizienten Berechenbarkeit den Mathematikern wohlbekannt. Das Konzept der Gültigkeit taucht seit langem in der Geradenstruktur und Kompassstruktur der griechischen Geometrie auf. Die Gültigkeit ist auch ein integraler Bestandteil des Entscheidungsproblems und des zehnten Hilbert-Problems. Das Geniale an Turings Konzept im Vergleich zu Gödels rekursiven Funktionen und Churchs Lambda-Kalkül ist, dass es offensichtlich richtig ist. Gödel selbst war sich nicht sicher, ob seine rekursive Funktion die Idee der Berechnung erfasste, und wir wissen nicht, ob Churchs Idee richtig war. Nur Turings Ideen waren einfach und natürlich. Turings Ideen sind nachweislich mit anderen Modellen gleichwertig und liefern für alle vernünftige Erklärungen. Auf diese Tatsache wies er in seiner Arbeit „Computability and Lambda-Definability“ von 1937 hin.

Ziel dieses Artikels ist es, die vom Autor vorgeschlagene berechenbare Funktion und die λ-definierbare Funktion#🎜🎜 von Qiu Qi zu beweisen #Und die allgemeine rekursive Funktion , die von Elbron und Gödel vorgeschlagen und von Kleiny entwickelt wurde, ist dieselbe. Dieselben Funktionen beweisen, dass jede X-definierte Funktion berechenbar ist und dass jede berechenbare Funktion im Allgemeinen rekursiv ist.

Beachten Sie, dass Turing „berechenbar“ geschrieben hat und wir „Turing berechenbar“ schreiben müssen.

Das obige ist der detaillierte Inhalt vonTuring-Maschine: Wie können wir über Computer sprechen, wenn es keine Computer gibt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!