Ist eine Turing-Maschine per Definition die leistungsstärkste Maschine?

54

Ich bin damit einverstanden, dass eine Turingmaschine "alle möglichen mathematischen Probleme" lösen kann. Das liegt aber daran, dass es sich nur um eine maschinelle Darstellung eines Algorithmus handelt: zuerst dies tun, dann das tun, schließlich das ausgeben.

Ich meine, alles, was lösbar ist, kann durch einen Algorithmus dargestellt werden (weil das genau die Definition von "lösbar" ist). Es ist nur eine Tautologie. Ich habe hier nichts Neues gesagt.

Und durch die maschinelle Darstellung eines Algorithmus ist es auch nichts Neues, alle möglichen Probleme zu lösen. Das ist auch bloße Tautologie. Wenn also gesagt wird, dass eine Turing-Maschine die leistungsstärkste Maschine ist, bedeutet dies effektiv, dass die leistungsstärkste Maschine die leistungsstärkste Maschine ist!

Definition von "mächtigste": Das, was jede Sprache akzeptieren kann.
Definition von "Algorithmus": Prozess für etwas zu tun. Maschinendarstellung von "Algorithmus": Eine Maschine, die alles kann.

Daher ist es nur logisch, dass die Maschinendarstellung eines Algorithmus die leistungsstärkste Maschine ist. Was ist das Neue, was Alan Turing uns gegeben hat?

Sounak Bhattacharya
quelle
9
Die Drehmaschine kann das Halteproblem nicht lösen. Es gibt jedoch keinen Beweis, dass es keine Maschine gibt, die das Problem löst. Das Modell ist eine Art TM mit Orakel oder völlig dofferent Ansatz. Wenn Sie der These der Kirche folgen, repräsentiert TM nur Maschinen, die wir heutzutage benutzen.
Eugene
16
Es ist die leistungsstärkste Maschine, die wir bauen können . Naja, eigentlich nein, wir können nur endliche Automaten bauen.
Raphael
13
Ihr Problem ist, dass Sie TMs als etwas betrachten, das danach kam. Es war nicht. Es wurde (und wird) verwendet, um die Klasse der Turing- berechenbaren Probleme zu definieren . Es wurden viele äquivalente Modelle gefunden, aber dies ändert nichts an der Definition.
Raphael
3
Es gibt Hunderte verschiedener (Turing-vollständiger) Computerarchitekturen, alle mit sehr unterschiedlichen Befehlssätzen. Ich glaube nicht , es ist offensichtlich, überhaupt , dass es kein Problem ist , dass man lösen kann , aber andere nicht.
BlueRaja - Danny Pflughoeft
5
... ist das, was Sie sagen, nicht einfach die kirchentürkische These ? Soweit wir wissen, hat niemand die These widerlegt , aber wir können nicht ausschließen, dass es ein anderes Berechnungsmodell gibt, das "vernünftig" (dh in gewisser Weise umsetzbar) und stärker als TMs ist.
Bakuriu

Antworten:

135

Ich bin damit einverstanden, dass eine Turingmaschine "alle möglichen mathematischen Probleme" lösen kann.

Das solltest du nicht, weil es nicht stimmt. Zum Beispiel können Turing-Maschinen nicht bestimmen, ob Polynome mit ganzzahligen Koeffizienten ganzzahlige Lösungen haben ( Hilberts zehntes Problem ).

Ist Turing Machine per Definition die leistungsstärkste Maschine?

Nein. Wir können uns eine unendliche Hierarchie leistungsstärkerer Maschinen ausdenken . Die Turing-Maschine ist jedoch die leistungsstärkste Maschine, die wir zumindest im Prinzip bauen können. Das ist jedoch keine Definition: Es ist nur so, dass wir keine Ahnung haben, wie man etwas Stärkeres baut oder ob es überhaupt möglich ist.

Was ist das Neue, was Alan Turing uns gegeben hat?

Eine formale Definition des Algorithmus. Ohne eine solche Definition (z. B. die Turing-Maschine) haben wir nur informelle Definitionen des Algorithmus im Sinne von "Eine endlich festgelegte Prozedur zum Lösen von etwas". OK, großartig. Aber welche einzelnen Schritte dürfen diese Verfahren unternehmen?

Sind Grundrechenarten Schritte? Ist das Ermitteln der Steigung einer Kurve eine Stufe? Ist das Finden von Polynomwurzeln ein Schritt? Ist es ein Schritt, ganzzahlige Wurzeln von Polynomen zu finden? Jeder von denen scheint ungefähr so ​​natürlich. Wenn Sie jedoch alle zulassen, sind Ihre "endlich festgelegten Prozeduren" leistungsfähiger als Turing-Maschinen. Dies bedeutet, dass sie Dinge lösen können, die nicht durch Algorithmen gelöst werden können. Wenn Sie alle bis auf den letzten zulassen, befinden Sie sich immer noch im Bereich der Turing-Berechnung.

Wenn wir keine formale Definition des Algorithmus hätten, könnten wir diese Fragen nicht einmal stellen. Wir könnten nicht diskutieren, was Algorithmen können, weil wir nicht wissen, was ein Algorithmus ist .

David Richerby
quelle
3
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
Meinen Sie nicht rationale Lösungen? Ich denke, dass ganzzahlige Lösungen in einer endlichen Anzahl von Schritten möglich sind.
Trenin
2
ein+ichbein,bZ
Verstanden. Außerdem ist das, was ich für möglich hielt, viel schwieriger als ich dachte.
Trenin
64

Sie haben nicht Recht, wenn Sie wiederholt Aussagen darüber machen, dass es sich bei diesem oder jenem um "nur eine Tautologie" handelt. Gestatten Sie mir, Ihre Behauptungen in einen historischen Kontext zu stellen.

Zunächst müssen Sie die verwendeten Konzepte präzisieren. Was ist ein Problem? Was ist ein Algorithmus? Was ist eine Maschine? Sie mögen denken, dass dies offensichtlich ist, aber ein Großteil der 1920er und 1930er Jahre wurde von Logikern verbracht, die versuchten, diese Dinge herauszufinden. Es gab mehrere Vorschläge, darunter Turing-Maschinen, die am erfolgreichsten waren. Es stellte sich später heraus, dass die anderen Vorschläge Turing-Maschinen entsprachen. Man muss sich eine Ära vorstellen, in der das Wort "Computer" eine Person bedeutet, keine Maschine. Sie reiten nur auf der Welle und den Konsequenzen der brillanten Erfindungen brillanter Köpfe von vor hundert Jahren, ohne sich dessen bewusst zu sein.

Turingmaschinen werden konkret in Form von Zuständen, einem Kopf und einem Arbeitsband beschrieben. Es ist alles andere als offensichtlich, dass dies die Rechenmöglichkeiten des Universums, in dem wir leben, erschöpft. Könnten wir nicht eine leistungsfähigere Maschine mit Strom, Wasser oder Quantenphänomenen bauen? Was ist, wenn wir eine Turing-Maschine mit der richtigen Geschwindigkeit und Richtung in ein Schwarzes Loch fliegen, damit sie unendlich viele Schritte in der für uns endlichen Zeit ausführen kann? Sie können nicht einfach "offensichtlich nicht" sagen - Sie müssen zuerst einige Berechnungen in der allgemeinen Relativitätstheorie durchführen. Und was ist, wenn die Physiker eine Möglichkeit finden, parallele Universen zu kommunizieren und zu steuern, sodass wir unendlich viele Turing-Maschinen gleichzeitig betreiben können?

Es spielt keine Rolle, dass wir diese Dinge derzeit nicht tun können. Wichtig ist jedoch, dass Sie verstehen, dass Turing darüber nachdenken musste, was physikalisch möglich war (basierend auf den damaligen Kenntnissen der Physik). Er schrieb nicht nur "eine bloße Tautologie" auf. Weit davon entfernt analysierte er sorgfältig, was Berechnung im informellen Sinne bedeutet, schlug dann ein formales Modell vor, argumentierte sehr sorgfältig, dass dieses Modell das erfasst, was Menschen unter "Berechnung" verstehen, und leitete einige wichtige Theoreme darüber ab. Einer dieser Theoreme besagt, dass Turing-Maschinen nicht alle mathematischen Probleme lösen können (im Gegensatz zu einer Ihrer falschen Aussagen). Dies alles in einem einzigen Artikel, der während der Sommerferien geschrieben wurde, als er noch Student war.war die Erfindung der Idee des modernen Allzweckcomputers. Danach war es nur noch eine einfache Techniksache.

Beantwortet das, was Turing über eine bloße Tautologie hinaus zur Menschheit beigetragen hat? Und hast du tatsächlich seine Zeitung gelesen ?

Andrej Bauer
quelle
19
"Man muss sich eine Ära vorstellen, in der das Wort" Computer "eine Person bedeutet, keine Maschine." Dies ist eine sehr hilfreiche Erinnerung. Im Wesentlichen versuchte Turing mit seiner "Maschine" die Operationen, die eine Person zu dieser Zeit mit Stift und Papier ausführen konnte, um etwas zu berechnen, effektiv zu simulieren.
Sorrop
2
"Sein Theorem über die Existenz von Universalmaschinen war die Erfindung des modernen Universalcomputers." - Na ja ... in der mathematischen Welt vielleicht. Menschen wie Konrad Zuse entwickelten eigenständig Allzweckcomputer.
Raphael
6
@AndrejBauer Das deutet immer noch auf eine Zeitleiste und Abhängigkeit hin, die nicht in allen Fällen vorhanden waren. Ich gebe dir keine Schuld - nur wenige Leute wissen, was Zuse wann getan hat. Fakt ist, er baute Computer von 1935 bis zum Ende des Zweiten Weltkriegs, ohne viel, wenn überhaupt, Input von außerhalb Deutschlands. In dieser Zeit entwickelte er auch seinen Plankalkül. Ich denke, es war mit Computern wie mit vielen anderen Dingen: Die Zeit war reif, so viele Köpfe dachten nach ähnlichen Grundsätzen. Trotz all seiner Beiträge hat Turing das Rechnen nicht erfunden .
Raphael
12
@Raphael: Konrad Zuse wusste nicht, dass seine Maschine alle berechenbaren Probleme verarbeiten kann (wir wissen jetzt, dass seine Maschinen vollständig funktionieren - Modulo-Speicher). Was Turing beitrug, war NICHT die Idee, dass Maschinen rechnen können - Babbage tat dies vor Zuse oder Turing. Was Turing beisteuerte, war die Idee, dass Befehlssätze und Programmiersprachen theoretisch keine Rolle spielen. Dies ist keine offensichtliche Idee. Ironischerweise ist es diese Idee, die die Entwicklung von CPUs und Programmiersprachen
vorantreibt
1
"Befehlssätze und Programmiersprachen spielen theoretisch keine Rolle" - das ist eindeutig falsch. Unterschiede können wichtig sein, aber nicht immer. Turing definierte ein bestimmtes Rechenmodell und behauptete, es sei so leistungsfähig, wie es nur geht. Ich bin mir nicht sicher, ob diese Behauptung Wasser enthält. In gewisser Weise tat er also nichts anderes als Zuse, wenn auch mit Mathematik anstelle von Metall.
Raphael
23

Dass "alles, was lösbar ist, durch einen Algorithmus dargestellt werden kann", ist überhaupt nicht offensichtlich.

Dies war Gegenstand intensiver Debatten, da Alan Turing, der die Ideen der Alonzo Church überarbeitete, eine Definition berechenbarer Zahlen vorschlug, die die Form der Maschine hatte, auf die Sie sich beziehen. Zu dieser Zeit arbeiteten nicht nur diese Leute an solchen Dingen.

Wir nennen es immer noch eine These - oder eine Vermutung - da "alles, was berechnet werden kann" eindeutig kein genaues mathematisches Objekt ist, dessen Struktur und Reichweite auf nicht spekulative Weise untersucht werden könnte.

André Souza Lemos
quelle
1
Aber alles, was lösbar ist, muss durch einen "Prozess" (per Definition) gelöst werden. Möglicherweise kennen wir den Prozess zur Lösung eines bestimmten "lösbaren" Problems zum gegenwärtigen Zeitpunkt nicht. In diesem Fall ist das Problem lösbar, kann aber jetzt nicht gelöst werden. Bedeutet dies nicht effektiv, dass "alles, was lösbar ist, durch einen Algorithmus dargestellt werden kann", weil "process" = "algorithm". Warum sagst du, dass es nicht offensichtlich ist?
Sounak Bhattacharya
13
Was ist ein "Prozess"? Sehen Sie, es ist einfach, im Kreis zu laufen und ein unklares Konzept durch ein anderes zu ersetzen. Turing-Versuch war eigentlich ein Gedankenexperiment, das auch heute noch unsere Vorstellungskraft beflügelt. Das ist keine Kleinigkeit.
André Souza Lemos
@SounakBhattacharya Durch einen Prozess (von Jahren und Genie) bewies Sir Andrew Wiles, dass Fermats letzter Satz wahr ist. Stellen Sie sich vor, dass es ein TM gibt, das diese Entscheidung hätte treffen können?
OJFord
1
@OllieFord Nun, wenn der Beweis so streng ist, dass jeder Schritt in Form vorhandener, gut spezifizierter Axiome ausgedrückt werden kann, kann der Beweis durch eine Turing-Maschine verifiziert werden. Wir könnten dann eine Turing-Maschine spezifizieren, die alle möglichen Beweise auflistet, und sicher (aber sehr, sehr langsam) würde die Maschine einen solchen Beweis finden. Eine einfache physische Implementierung dieser Turing-Maschine würde jedoch mehr als 400 Jahre dauern und viel länger als die erwartete Lebensdauer des Universums.
2.
19

Zunächst ist zu bedenken, dass Turing-Maschinen ursprünglich von Turing nicht als Modell eines physikalisch realisierbaren Computers konzipiert wurden, sondern als ideale Grenze dessen, was ein Mensch mit einer schrittweisen mechanischen Berechnung berechnen kann Art und Weise (ohne Verwendung von Intuition). Dieser Punkt wird weitgehend missverstanden - siehe [1] für eine hervorragende Darstellung zu diesem und verwandten Themen.

Die von Turing für seine Turingmaschinen postulierten Endlichkeitsbeschränkungen beruhen auf postulierten Beschränkungen des menschlichen Sinnesapparates. Verallgemeinerungen von Turings Analysen auf physikalisch realisierbare Computergeräte (und ähnliche Church-Turing-Thesen) kamen erst viel später (1980) aufgrund von Robin Gandy - mit Einschränkungen aufgrund der Gesetze der Physik. Wie Odifreddi auf p sagt. 51 von [2] (Bibel der klassischen Rekursionstheorie)

Turingmaschinen sind theoretische Geräte, wurden jedoch mit Blick auf physikalische Einschränkungen entwickelt. Insbesondere haben wir in unser Modell Einschränkungen aufgenommen, die sich aus folgenden Gründen ergeben:

  • (a) ATOMISMUS, indem sichergestellt wird, dass die Informationsmenge, die in jeder Konfiguration der Maschine (als endliches System) codiert werden kann, begrenzt ist; und

  • (b) RELATIVITÄT durch Ausschließen von Fernaktionen und Vermehrung der kausalen Wirkung durch lokale Interaktionen. Gandy [1980] hat gezeigt, dass der Begriff der Turing-Maschine allgemein genug ist, um jedes Computergerät, das ähnliche Einschränkungen erfüllt, in einem genauen Sinne zu subsumieren.

und auf p. 107: (Eine allgemeine Theorie diskreter, deterministischer Geräte)

Die Analyse (Church [1957], Kolmogorov und Uspenskii [1958], Gandy [1980]) geht von den Annahmen des Atomismus und der Relativität aus. Ersteres reduziert die Struktur der Materie auf einen endlichen Satz von Grundpartikeln mit begrenzten Dimensionen und rechtfertigt somit die theoretische Möglichkeit, eine Maschine auf einen Satz von Grundbestandteilen zu zerlegen. Letzteres setzt der Ausbreitungsgeschwindigkeit von kausalen Veränderungen eine Obergrenze (Lichtgeschwindigkeit) auf und rechtfertigt somit die theoretische Möglichkeit, den in einem Moment t auf einen begrenzten Raumbereich V erzeugten kausalen Effekt auf Aktionen zu reduzieren, die von den Bereichen erzeugt werden deren Punkte sich in der Entfernung c * t von einem Punkt V befinden. Natürlich berücksichtigen die Annahmen keine Systeme, die kontinuierlich sind oder die ein unbegrenztes Einwirken in der Ferne ermöglichen (wie die Newtonschen Gravitationssysteme).

Die Analyse von Gandy zeigt, dass DAS VERHALTEN FÜR JEDES GERÄT MIT EINEM FESTEN GRUND FÜR DIE KOMPLEXITÄT SEINER MÖGLICHEN KONFIGURATIONEN (in dem Sinne, dass sowohl die Ebene des konzeptuellen Aufbaus aus Bestandteilen als auch die Anzahl von Bestandteilen in irgendeinem strukturierten Teil von Jede Konfiguration ist begrenzt.) UND FESTE ENDLICHE, DETERMINISTISCHE ANWEISUNGEN FÜR LOKALE UND GLOBALE MASSNAHMEN (die erstere beschreibt, wie die Wirkung einer Aktion auf strukturierte Teile zu bestimmen ist, die letztere, wie die lokalen Effekte zusammenzusetzen sind). Darüber hinaus ist die Analyse dahingehend optimal, dass jede Lockerung der Bedingungen mit jedem Verhalten vereinbar ist, wenn sie präzisiert wird, und liefert somit eine ausreichende und notwendige Beschreibung des rekursiven Verhaltens.

Gandys Analyse gibt einen sehr aufschlussreichen Überblick über die Leistung und die Einschränkungen von Turing Machines. Es lohnt sich zu lesen, um weitere Einblicke in diese Fragen zu erhalten. Seien Sie jedoch gewarnt, dass die Arbeit von Gandy aus dem Jahr 1980 [3] selbst von einigen Cognoscenti als schwierig angesehen wird. Es kann hilfreich sein, zuerst die Artikel in [4] von J. Shepherdson und A. Makowsky zu lesen.

[1] Sieg, Wilfried. Mechanische Verfahren und mathematische Erfahrung. [S. 71-117 in Mathematik und Verstand. Vorträge von der Konferenz über die Philosophie der Mathematik am Amherst College, Amherst, Massachusetts, 5.-7. April 1991. Herausgegeben von Alexander George. Logic Comput. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Rezensent: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Klassische Rekursionstheorie. Die Theorie der Funktionen und Mengen natürlicher Zahlen. Mit einem Vorwort von GE Sacks. Studium der Logik und der Grundlagen der Mathematik, 125. North-Holland Publishing Co., Amsterdam-New York, 1989. xviii + 668 S. ISBN: 0-444-87295-7 MR 90d: 03072 (Rezensent: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. These und Prinzipien der Kirche für Mechanismen. Das Kleene-Symposium. Vorträge des Symposiums an der University of Wisconsin, Madison, Wisconsin, 18.-24. Juni 1978. Herausgegeben von Jon Barwise, H. Jerome Keisler und Kenneth Kunen. Studium der Logik und der Grundlagen der Mathematik, 101. North-Holland Publishing Co., Amsterdam-New York, 1980. xx + 425 S. ISBN: 0-444-85345-6 MR 82h: 03036 (Rezensent: Douglas Cenzer) 03D10 (03A05)

[4] Die universelle Turingmaschine: eine Umfrage aus einem halben Jahrhundert. Zweite Ausgabe. Hrsg. Von Rolf Herken. Computerkultur, II. Springer-Verlag, Wien, 1995. xvi + 611 S. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)

Bill Dubuque
quelle
2
Vielen Dank! Ich hatte immer das Gefühl, dass Turing-Maschinen seltsamerweise unelegant sind, aber dies erklärt auf faire Weise, warum dies falsch verstanden werden kann.
PJTraill
6

Die populärste Diskussion über diese Frage, die ich je gelesen habe, ist der Aufsatz von MIT-Professor Scott Aaronson. Wer kann die größere Zahl nennen? , in dem er unter anderem die Auswirkungen von Super-Turing-Maschinen, Super-Duper-Turing-Maschinen und Super-Duper-Pooper-Turing-Maschinen untersucht.

James Brock
quelle
2
Nach "Super-Duper-Pooper" kommt "Super-Duper-Ooper-Flooper", oder zumindest ist es das, woran ich mich zu erinnern scheine, als ich 7 oder 8 Jahre alt war. Es ist wahrscheinlich die richtige formale Terminologie.
Peter Cordes
4

Nein, TMs sind nicht besonders leistungsfähig. Zwei Beispiele:

a) Es könnte andere Maschinen geben, die die gleichen Ergebnisse wie ein TM berechnen, jedoch algorithmisch schneller (z. B. Quantencomputer, die Primfaktoren berechnen). "Schneller" ist eine Art Kraft.

b) TMs können keine allgemeinen reellen Zahlen mit perfekter Genauigkeit darstellen. Ein analoger Computer (AC) kann jedoch möglicherweise mit reellen Zahlen mit perfekter Genauigkeit arithmetisch arbeiten. Dies wäre leistungsstärker als jedes TM.


Natürlich erfordert (b), dass unser Universum einige stetige Eigenschaften (Schwerkraft?) Hat, mit denen der Wechselstrom reelle Werte darstellen kann. Vielleicht wird jede physikalische Eigenschaft, einschließlich der Schwerkraft, quantisiert. Aber wir können über Maschinen in einem kontinuierlichen Universum spekulieren. TMs sind also "per Definition" nicht besonders leistungsfähig.

Adam Gawne-Cain
quelle
3
Willkommen auf der Seite! "Stärker" im Kontext der Berechnungstheorie bedeutet normalerweise "in der Lage, mehr Funktionen zu berechnen", anstatt "in weniger Schritten zu berechnen", daher bin ich mir nicht sicher, ob Ihr (a) wirklich zählt. Es ist auch nicht klar, wie ein Computer reale Werte verwenden könnte. Wie würden Sie einen reellen Wert eingeben, der beispielsweise kein berechenbarer reeller Wert ist? Wie würden Sie anderen mitteilen, welchen Wert sie für ihre Endlosmaschine eingeben sollen, und wie würden Sie mit Geräuschen umgehen? Aber vielleicht ist das ein dummer Einwand wie: "Wie würden Sie genug Klebeband für die Turing-Maschine produzieren?".
David Richerby
-4

Wenn Sie sich die Komplexität der Berechnungen ansehen, ist eine Turing-Maschine die leistungsstärkste Maschine - weil sie über unbegrenzten Speicher verfügt und keine echte Maschine über diesen verfügt. Jede reale Maschine kann keine Probleme beliebiger Größe lösen. Sie können ein Problem nicht einmal lesen , geschweige denn lösen.

Wenn Sie andererseits versuchen, eine echte Turing-Maschine zu implementieren, nehmen wir an, dass sie stoppt und einen Alarm auslöst, wenn das Band ausgeht, und Sie feststellen, dass für jede Art von Berechnung viel mehr Schritte erforderlich sind als lassen Sie uns die reale Maschine in einem billigen Telefon sagen, und wäre viel viel langsamer bei der Lösung von realen Problemen. Sie werden auch feststellen, dass das Schreiben einer Antwort auf ein Band keine sehr gute Benutzeroberfläche ist. Und Sie werden feststellen, dass viele Menschen Computer nicht zum Lösen von Problemen, sondern zum Senden von Nacktfotos an ihre Freunde und zum Ansehen von Katzenvideos verwenden, und eine Turing-Maschine ist dafür überhaupt nicht geeignet.

gnasher729
quelle
12
Können Sie klarstellen, wie dies die Frage beantwortet?
David Richerby
1
Natürlich kann eine echte Turing-Maschine Fotos und Videos verarbeiten. Es wäre natürlich eine Art Bildausgabegerät erforderlich, damit Menschen sie sehen können, aber das gilt für jeden Computer. ein CPU + Speicher auf einer Platine ist auch nicht "überhaupt nicht zu gebrauchen".
Hyde
1
Unter den Maschinenmodellen mit unbegrenztem Speicher sind TMs nicht die leistungsstärksten!
Raphael