Kann der Geist ein endlicher Automat sein und trotzdem die Turing-Maschine erfinden?

7

Die Turing-Maschine wurde von einem menschlichen Verstand erfunden. Vermutlich kann nichts weniger Leistungsfähiges als eine Turingmaschine eine Turingmaschine erfinden.

Eine Turing-Maschine hat jedoch unendlich viel Band, während sich der Geist in einem endlichen Universum befindet und daher nur ein TM mit endlichem Band sein kann. Ein TM mit endlichem Band kann durch endliche Automaten simuliert werden, die strikt weniger leistungsfähig sind als eine Turingmaschine. Dies scheint zu implizieren, dass eine Turing-Maschine von einem Automaten erfunden wurde, der weniger leistungsfähig ist als eine Turing-Maschine, was der ursprünglichen Prämisse widerspricht.

Ist das ein Problem? Oder ist die ursprüngliche Prämisse falsch? Ist es möglich, dass endliche Automaten eine Maschine "erfinden", die leistungsfähiger ist, eine Art Bootstrapping, wenn Sie so wollen?

Während es schwierig ist, "erfinden" formal zu definieren, scheint es nicht, dass endliche Automaten sogar endliche TMs effektiv darstellen können. Auf der Wikipedia-Seite heißt es beispielsweise, dass ein DFA Billiarden von Zuständen benötigt , um ein TM mit einigen hundert Zuständen darzustellen. Um nur die nützliche Teilmenge des Anhaltens von TMs darzustellen, habe ich den Eindruck, dass eine DFA-Darstellung wahrscheinlich unsere Rechenkapazität übersteigt. Es scheint eine große Trennung zwischen DFAs und TMs zu geben, so dass es kaum vorstellbar ist, dass ein plausibles Bootstrapping von einem zum anderen wechselt.

Es gibt auch die damit verbundene Frage, wie endliche Automaten das Stoppproblem für TMs beweisen können.

yters
quelle
1
Die Mathematik ist ein endliches (in endloser Zeit aufzählbares) System, dessen Objekte, beginnend mit den reellen Zahlen, weitaus unendlicher sein können. Wie kann Mathematik existieren?
Vorschaubild
Vielleicht stützen Sie Ihre Analyse auf die falschen Annahmen, dass das menschliche Gehirn ein endliches Band hat :)
Federico Ponzi

Antworten:

3

Sie haben in der Tat ein Prämissenproblem. Wir sind keine FSMs oder TMs. Vergessen Sie nicht, dass alle diese rechentheoretischen Geräte einfache mathematische Abstraktionen sind, die aus einer Reihe von Axiomen und begrenzten Eingaben bestehen. Die rechentheoretischen Systeme (von Godel, Turing und Church) sollen lediglich den Nachweis erbringen, ob bestimmte Arten von Funktionen berechenbar sind oder nicht.

Im Gegensatz dazu:

  1. Filtern Sie durch buchstäblich unendliche Informationen
  2. Bewusstsein besitzen (was auch immer das bedeutet)
  3. existieren in der physischen Welt

Ein einfacher Beweis dafür, dass wir keine TMs sind, ist das, was Sie gerade skizziert haben: Wir können Turing-Maschinen erfinden, aber Turing-Maschinen können uns nicht nacheinander erfinden. Es ist für uns absolut trivial, den Endpunkt einer Unendlichkeit von TM-Konfigurationen zu sehen, bevor sie ausgeführt werden (obwohl es auch unendlich viele TMs gibt, für die wir den Endpunkt nicht sehen können), aber kein TM kann den Endpunkt eines Menschen trivial bestimmen, bevor er oder sie Leben.

Es gibt ein Sprichwort aus der Kartographie, das hier sehr nützlich sein kann: Die Karte ist nicht das Territorium

Diese axiomatischen Systeme sind sehr geschickt entwickelt, um auf einige winzige (wenn auch wichtige) Ideen zuzugreifen, aber der Versuch, einen Menschen auf das 7-Tupel und die kurze Reihe von Axiomen einer Turing-Maschine zu reduzieren, ist ungefähr so ​​sinnvoll wie das Reduzieren des Menschen auf eine andere Zusammenfassung axiomatisches System. Während diese Systeme nützlich sind, um Aspekte der realen Welt zu sehen, sind sie keine vollständigen Bilder, und wir sind nicht mehr Finite-State-Maschinen oder Turing-Maschinen als Zahlentheorie oder Mengenlehre.

Ben I.
quelle
Es ist ziemlich fraglich, dass wir durch unendliche Informationen filtern. In der realen Welt mag es unendlich viele Informationen geben, aber nur eine begrenzte Menge davon wird von unseren Sinnen erfasst. Alle unsere Sinne haben eine begrenzte Auflösung.
jmite
Es ist trotzdem wahr. Es gibt zu jedem Zeitpunkt unendlich viele Dinge, auf die Sie Ihre Aufmerksamkeit (Ihre primäre Filtermethode) sowohl intern als auch extern richten können. Sie können sogar Ihre Aufmerksamkeit auf die Dinge , die Ihre Sinne nicht direkt erkennen kann, und als Spezies, haben wir eine Neigung zu Möglichkeiten der Umwandlung praktisch alles , was von diesem nicht nachweisbare Menge von Informationen in etwas zu finden , dass wir letztlich kann erkennen.
Ben I.
Dies sind gute Punkte, aber Menschen existieren im physischen Universum und alle physikalischen Gesetze können auf einer Turing-Maschine simuliert werden. Es scheint also, dass Menschen zumindest auf Turingmaschinen reduziert werden können. Wie kann ein Mensch auf ein TM reduziert werden und dennoch zu Aktionen fähig sein, die ein TM nicht ausführen kann? Entweder ist die Reduktion unmöglich und Menschen sind bis zu einem gewissen Grad nicht physisch, oder TMs können alles, was Menschen tun können.
Yters
1
Die Natur kann jedoch nur einen Kreis mit einer Auflösung bis zur Plankenlänge erstellen. Eine echte Debatte ist, wenn die Naturgesetze, wie wir sie jetzt verstehen, lediglich Transformationen von Informationen von einem Staat zum nächsten beschreiben, was dann den Staat ausmacht.
Devendra Bhave
1
@yters, Es ist eindeutig möglich, dass nicht alles im Universum vollständig deterministisch ist. Ich habe den Kollaps von Quantenwellenfunktionen als Beispiel verwendet, nicht weil er unbestimmt ist, sondern weil derzeit offen ist, ob er deterministisch ist. Auch wenn sich herausstellt, dass dies keine Garantie für den Rest des Universums gibt. Zweitens ist die einzige Schlussfolgerung, die ich aus "alles ist genau modellierbar" sehen kann, dass dann das gesamte Universum ein FSM ohne weitere Eingabe ist; wir rennen einfach weiterϵÜbergänge, bis wir irgendwann entweder anhalten oder schleifen.
Ben I.
6

Einige Details der Turingmaschine

  • Eine Turingmaschine hat kein unendliches Band, sondern unbegrenztes Band. Es gibt keine Begrenzung, wie viele Symbole darauf gespeichert werden können, aber zu einem bestimmten Zeitpunkt befindet sich immer nur eine begrenzte Anzahl von Symbolen auf dem Band. Während wir uns also nicht alle Läufe einer Maschine vorstellen können, können wir uns immer zumindest einige Zustände der Maschine vorstellen.
  • In gewissem Sinne schneiden Turing-Maschinen den "endlichen" Teil aller Sprachen heraus, in dem Sinne, dass sie den Teil herausschneiden, der endlich dargestellt werden kann (durch eine Turing-Maschine). Es gibt unzählige Sprachen, aber unzählige Turing-Maschinen, also gibt es eine Menge Dinge, die wir nie verstehen werden, weil sie wirklich unendlich sind, in einer zu großen Unendlichkeit.
  • Die meisten Probleme, die wir uns vorstellen können, erfordern nicht die Leistung einer Turingmaschine. Viele können mit primitiver Rekursion oder anderen fundierten Rekursionsschemata geschrieben werden. Die meisten Algorithmen erfordern also nicht die Unendlichkeit von Turing-Maschinen.
  • Für eine Turing-Maschine, die anhält, gibt es immer eine Funktion, die die maximale Speichermenge beschreibt, die im Verhältnis zur Eingabegröße verwendet wird. Wir müssen also nicht die Unendlichkeit verstehen, sondern nur die Beziehung verstehen.

Kann ein schwaches System ein stärkeres erfinden?

Ich denke, die Antwort hier lautet ja, abhängig von Ihrer Definition. Zum Beispiel kann die Sprache aller gültigen Turingmaschinen mit einer kontextfreien Grammatik beschrieben werden, einer rechnerisch schwächeren Formalisierung. Sie können sogar eine reguläre Sprache beschreiben, die beschreibt, wie eine gültige Turingmaschine aussieht, und die endlich ist. (Spoiler-Alarm, das sagt nicht viel, da Sie jede Ganzzahl einer Turing-Maschine zuordnen können, also der regulären Sprache{0,1} kann die Menge aller gültigen Turingmaschinen sein).

Und es ist wichtig zu unterscheiden, ob man etwas erkennt oder eine Beschreibung von etwas erfindet und alle Dinge erfindet. Wir können erkennen, was eine Turing-Maschine ist, aber wir können nicht alle sehen, und aufgrund von Dingen wie dem Halting-Problem können wir sicherlich nicht alle verstehen.

Andere unendliche Dinge

Diese Frage unterscheidet sich letztendlich nicht von der Frage, wie ein endlicher Verstand die natürlichen Zahlen oder die Funktion verstehen kann y=x im R2. Beide sind unendlich, können aber auf endliche Weise beschrieben werden.

Aber es gibt Funktionen und Mengen und reelle Zahlen und solche, die wirklich unendlich sind und die niemals durch eine mögliche gesprochene oder geschriebene Formel beschrieben werden können (weil es in jeder menschlichen Sprache unzählige reelle, aber zählbar viele endliche Sätze gibt.) Und dort Es gibt mehr wahre Theoreme als Beweise, a la Gödel.

So können wir die Unendlichkeit beschreiben und über ihre Eigenschaften sprechen, vielleicht ohne sie wirklich zu verstehen, zumindest ohne jede Facette davon zu verstehen.

jmite
quelle
Während es schwierig ist, "erfinden" formal zu definieren, scheint es nicht, dass endliche Automaten sogar endliche TMs effektiv darstellen können. Auf der Wikipedia-Seite heißt es beispielsweise, dass ein DFA Billiarden von Zuständen benötigt, um ein TM mit einigen hundert Zuständen darzustellen. Um nur die nützliche Teilmenge des Anhaltens von TMs darzustellen, habe ich den Eindruck, dass eine DFA-Darstellung wahrscheinlich unsere Rechenkapazität übersteigt. Es scheint eine große Trennung zwischen DFAs und TMs zu geben, so dass es schwer vorstellbar ist, dass ein plausibles Bootstrapping von einem zum anderen wechselt.
Yters
@yters Aber das ist der Punkt meiner Antwort. Es gibt einen großen Unterschied zwischen der Fähigkeit, alle Schritte einer Turingmaschine zu simulieren, und der Fähigkeit zu simulieren, was es bedeutet, eine Turingmaschine zu sein. Sie können eine Turing-Maschine endlich darstellen, ohne sie auszuführen. DFAs sind schlecht darin, Turing-Maschinen zu betreiben, aber sie können gut verstehen, was es bedeutet, eine Turing-Maschine zu sein.
Jmite