Menschliche Rechenleistung: Können Menschen das Stopp-Problem bei Turing Machines entscheiden?

60

Wir wissen, dass das Stopp-Problem (bei Turing-Maschinen) für Turing-Maschinen nicht zu entscheiden ist. Gibt es Forschungen darüber, wie gut der menschliche Verstand mit diesem Problem umgehen kann, möglicherweise unterstützt durch Turing Machines oder Allzweckcomputer?

Hinweis : Natürlich kann man im engeren Sinne immer nein sagen, da es Turing-Maschinen gibt, die so groß sind, dass sie nicht einmal in der Lebensspanne eines einzelnen Menschen gelesen werden können. Dies ist jedoch eine unsinnige Einschränkung, die nicht zur eigentlichen Frage beiträgt. Um die Dinge auszugleichen, müssten wir Menschen mit einer willkürlichen Lebensspanne annehmen.

Wir könnten also fragen: Wenn eine Turing-Maschine T in geeigneter Weise dargestellt wird, kann ein beliebig langlebiger Mensch H und eine beliebige Menge Puffer (dh Papier + Stifte) H entscheiden, ob T an dem leeren Wort anhält?


Fazit: Wenn die Antwort ja ist, würde sich das dann nicht auch erledigen, wenn irgendein Computer die Chance hat, den Turing-Test zu bestehen?

Bitmaske
quelle
15
Menschen können möglicherweise herausfinden, ob einige bestimmte Maschinen anhalten. Aufgrund der Unentscheidbarkeit des Halteproblems und der These von Church-Turing gibt es jedoch kein algorithmisches Verfahren, mit dem ein Mensch das Problem lösen könnte.
Carl Mummert
6
@CarlMummert: Menschen haben Einfallsreichtum; Dieser Einfallsreichtum ist nicht unbedingt an das gebunden, was Sie in Bezug auf ein TM ausdrücken können. Der Grund, warum die HP für TM unentscheidbar ist, ergibt sich aus dem Widerspruch in der diagonalen Sprache.
Bitmaske
4
Wenn die Menschen die Macht hätten, herauszufinden, welche Eingaben eine gegebene Turing-Maschine unterbricht, hätten sie wahrscheinlich nicht das Bedürfnis gehabt, die Definition einer Turing-Maschine oder der Klassen P und NP usw. so zu artikulieren , wie sie es tun würden Meist scheinen uns Neugierde, ganz triviale Probleme zu beschreiben. (Wenn Sie in einer großzügigen Stimmung sind, kann dies natürlich als Beschreibung unserer Beziehung zu deterministischen endlichen Automaten angesehen werden.)
Niel de Beaudrap
6
@ NieldeBeaudrap: Ich bin anderer Meinung. Obwohl wir zu etwas fähig sein könnten, könnte es immer noch eine anspruchsvolle Aufgabe sein (das Wort "hart" zu vermeiden). Wenn wir uns nicht richtig konzentrieren, neigen wir dazu, leichtsinnige Fehler zu machen, insbesondere bei langwierigen Aufgaben.
Bitmaske
8
Ich denke, die beste und einzige Antwort auf Ihre Frage ist, dass niemand weiß. Niemand weiß, ob die These von Church-Turing wahr ist oder welche Einschränkungen für das, was Menschen berechnen können, bestehen. Wir können sagen, dass Menschen, die das Stopp-Problem lösen können, etwas tun, was Turing-Maschinen nicht können.
Patrick87

Antworten:

28

Es ist sehr schwer, einen menschlichen Geist mit einer solchen mathematischen Genauigkeit zu definieren, wie es möglich ist, eine Turing-Maschine zu definieren. Wir haben noch kein funktionierendes Modell eines Mausgehirns, aber wir haben die Hardware, die es simulieren kann. Eine Maus hat ungefähr 4 Millionen Neuronen in der Großhirnrinde. Ein Mensch hat 80-120 Milliarden Neuronen (19-23 Milliarden neokortikal). Sie können sich also vorstellen, wie viel mehr Forschung erforderlich sein wird, um ein funktionierendes Modell des menschlichen Geistes zu erhalten.

Sie könnten argumentieren, dass wir nur von oben nach unten vorgehen müssen und nicht die einzelnen Funktionen jedes Neurons verstehen müssen. In diesem Fall könnten Sie nicht-monotone Logik, abduktives Denken, Entscheidungstheorie usw. studieren. Wenn die neuen Theorien auftauchen, treten mehr Ausnahmen und Paradoxien auf. Und es scheint, dass wir einem Arbeitsmodell eines menschlichen Geistes nicht nahe kommen.

Nachdem ich die Aussagen- und dann die Prädikatenrechnung genommen hatte, fragte ich meinen Logikprofessor:
"Gibt es eine Logik, die die gesamte Menge der menschlichen Sprache definieren kann?"
Er sagte:
"Wie würdest du Folgendes definieren?
Um eine Welt in einem Sandkorn
und einen Himmel in einer wilden Blume zu sehen,
halte die Unendlichkeit in deiner Handfläche
und die Ewigkeit in einer Stunde.
Wenn du es schaffst, wirst du es tun." berühmt werden."

Es gab Debatten darüber, dass ein menschlicher Verstand einer Turing-Maschine gleichwertig sein könnte. Ein interessanteres Ergebnis wäre jedoch, dass ein menschlicher Verstand nicht Turing-äquivalent wäre und eine Definition eines Algorithmus entstehen würde, der möglicherweise von einer Turing-Maschine nicht berechenbar ist. Dann würde die These der Kirche nicht stimmen und es könnte möglicherweise einen allgemeinen Algorithmus geben, der ein Stopp-Problem lösen könnte.

Bis wir mehr verstehen, finden Sie vielleicht einige Einblicke in einen Zweig der Philosophie. Es wird jedoch allgemein keine Antwort auf Ihre Frage akzeptiert.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

Dávid Natingga
quelle
Wäre es nicht ausreichend zu beweisen, dass Moleküle "berechenbar" sind, wenn das Gehirn als eine Ansammlung von Molekülen modelliert werden kann, die miteinander interagieren? Es scheint Beweise für diese Annahme zu geben (siehe OpenWorm).
Olivier Lalonde
@OlivierLalonde Ihre Annahme würde bedeuten, dass Menschen von einer Turing-Maschine simuliert werden können und daher das Halteproblem nicht lösen können. Ihre Annahme ist jedoch zu stark. Nach dem Unsicherheitsprinzip en.wikipedia.org/wiki/Uncertainty_principle in der Quantenmechanik kann der Zustand des physikalischen Systems auf einem Computer nicht simuliert werden, da eine zufällige Folge von Zuständen nicht berechnet werden kann. Sie können dann argumentieren, dass das Modell des physikalischen Systems deterministisch ist - nicht einfach. Die Frage reduziert sich darauf, ob eine Simulation eines Gehirns berechenbar ist.
Dávid Natingga
@DavidToth Eine zufällige unendliche Folge von Zuständen ist nicht berechenbar. Jedes System, das eine endliche Anzahl von Ereignissen enthält, ist berechenbar, vorausgesetzt, dass alle Größen in diesem System in Bezug zueinander berechenbar sind. Und selbst wenn dies nicht der Fall wäre, würden wir am Ende einfach einen Rundungsfehler haben, der kleiner als das thermische Rauschen ist und keinen signifikanten Einfluss auf die menschliche Wahrnehmung haben sollte. (Der Fehler wäre in der Tat unermesslich klein.)
Keen
@Cory Ja, jede endliche Teilmenge jeder Menge, selbst eine nicht berechenbare, ist berechenbar, aber es geht darum, "die Zukunft zu simulieren", um die Vergangenheit nicht noch einmal abzuspielen. In diesem Sinne gibt es möglicherweise keine Turing-Maschine, die eine menschliche Handlung in einer willkürlich entfernten Zeit in der Zukunft vorhersagen würde. Es müsste eine der Kombinationen einer unendlichen Folge zukünftiger Ereignisse vorhergesagt werden. Die Tatsache, dass die Anzahl der möglichen Ereignisse auf einmal endlich sein kann, ändert nichts an der Unberechenbarkeit der unendlichen Folge.
Dávid Natingga,
2
@DavidToth Ich behaupte nicht, dass die gesamte Realität für Turing berechenbar ist. Das Argument der Quantenzufälligkeit ist jedoch nicht haltbar. Die Quantenmechanik ist ein System, mit dem Physiker Eigenschaften zukünftiger Realitätszustände berechnen. Die (berechenbaren) Modelle der Physiker können mit dieser Zufälligkeit umgehen, da die Anzahl der (unterscheidbaren) Ergebnisse auch in Fällen, in denen sie unendlich sind, immer abzählbar (und damit berechenbar) ist. Man beachte, dass es auch keinen Grund gibt zu glauben, dass Quanten-Zufälligkeit dem Menschen und nicht anderen Maschinen die Fähigkeit geben würde, nicht berechenbare Funktionen zu bewerten.
Keen
16

Ich denke, es gibt keine Möglichkeit, eine endgültige Antwort auf diese Frage zu geben, da niemand die Fähigkeiten des menschlichen Geistes wirklich kennt (und ich bezweifle, dass es jemals jemandem gelingt).

Es gibt jedoch eine Ansicht, die eine mögliche Lösung oder Erklärung für diese Frage bietet:

Wenn wir ein Orakel suchen, um das Halteproblem zu lösen (oder die Beweisbarkeit logischer Formeln erster Ordnung usw. zu bestimmen), möchten wir natürlich, dass das Orakel korrekt ist , es darf keine Fehler machen. Aber der menschliche Geist ist nicht konsequentEs macht Fehler. Niemand kann ehrlich sagen, dass alle Aussagen, die er für wahr hält, wirklich wahr sind. Diese Inkonsistenz kann als die Quelle der Kraft angesehen werden, die der menschliche Geist besitzt. Aufgrund seiner Inkonsistenz unterliegt es keinen Einschränkungen, die sich aus dem Halteproblem, Gödels Unvollständigkeitssatz usw. ergeben. Wir machen Fehler, glauben fälschlicherweise an falsche Aussagen und korrigieren sie mit zunehmendem Wissen (und finden natürlich neue) falsche Aussagen, an die wir glauben). Andererseits wollen wir, dass alle Formalisierungen des Algorithmusbegriffs oder aller logischen Kalküle konsistent sind, damit wir ein für alle Mal beweisen können, dass sie frei von solchen Fehlern sind. Und das macht sie begrenzt.

Petr Pudlák
quelle
Wir machen nicht mehr Fehler als unsere Beweissysteme. Es ist durchaus üblich, auch in der Mathematik an Hypothesen zu arbeiten. Manchmal führen sie zu nachweislich falschen Ergebnissen (oder Beobachtungsfehlern in den Naturwissenschaften), und wir überarbeiten unsere Überzeugungen und einige unserer Arbeitshypothesen. In der Mathematik ist dies die Grundlage für den Beweis durch reductio ad absurdum (die nicht konstruktiv sind). Nicht deterministische Automaten stützen sich auch auf die Idee, dass man auch bei der Erforschung falscher Pfade Ergebnisse erzielen kann, solange man auch andere Pfade erkunden kann. Nichts dort unterscheidet den menschlichen Verstand.
Babou
Interessanter Punkt über die Möglichkeit der Inkonsistenz als eine Quelle der (rechnerischen) Kraft des Geistes. Ist Ihnen der Gedanke gekommen, dass es sogar Denkarten jenseits der Mathematik gibt, bei denen zwei offensichtlich widersprüchliche Daten zutreffen könnten? Die Qualität von "Wahrheit" als relativer Begriff, dem keine Zahl zugewiesen werden kann, ist eine Unterscheidung des menschlichen Denkens, die sich in einer Maschine nur schwer (wage ich zu sagen, unmöglich?) Vollständig reproduzieren lässt. Der Punkt, der darin besteht, mentale Inkonsistenz als "falschen Glauben an Falschheit" zu definieren (wie Sie es hier zu tun scheinen), ist selbst eine eher begrenzte Sichtweise.
Wildcard
Es kann gezeigt werden, dass man nicht beweisen kann, dass man sich niemals irren wird, aber das bedeutet nicht, dass man beweisen kann, dass man niemals einen Fehler machen wird. Nehmen wir zum Beispiel an, unser Universum ist ein Conway-Spiel der Lebenssimulation, das nicht der Theorie vieler Welten folgt. Angenommen, Sie geben an, dass Sie niemals einen Fehler gemacht haben und auch niemals machen werden. Dann wird ein bestimmter Algorithmus erst angehalten, nachdem Sie angegeben haben, dass dieser Algorithmus nicht angehalten wird. Wenn Sie ein ausreichend starkes System verwenden, können Sie daraus schließen, dass Sie niemals sagen werden, dass es nicht anhalten wird, und dass es daher niemals anhalten wird, und angeben, dass es dazu führt, dass es anhält.
Timothy
11

Nur um es klar zu machen: Die Church-Turing-Hypothese hat nichts mit einem Dogma einer hypothetischen Church of Turing zu tun. Daran ist nichts Religiöses. Im Gegenteil, es ist nur eine Hypothese, die unser bestes Wissen zusammenfasst. Es gibt keine metaphysischen Implikationen. Die Frage, ob Menschen mehr können als Maschinen, ist eine metaphysische Frage, da wir absolut keine Ahnung haben, was einen Menschen von einer Maschine unterscheiden könnte. Daher sollte diese Frage nach metaphysics.stackexchange.com migriert werden.

Nehmen wir jedoch an, dass das menschliche Gehirn das Halteproblem für Turing Machine lösen kann. Dann wird das Rechenmodell von Turing-Maschinen viel weniger wichtig und die Church-Turing-Hypothese wird viel weniger relevant, da wir ein leistungsfähigeres Modell haben, das Human-Modell (um das Wort Maschine zu vermeiden ). Natürlich hat dieses (beliebig langlebige) menschliche Modell eine eigene Hypothese zur Berechenbarkeit.

Während das Problem des Anhaltens für Turing Machines nicht länger kritisch ist, müssen wir uns nun mit dem Problem des Anhaltens des menschlichen Modells befassen. Und die Diagonalisierung wird zeigen, dass das Problem des Anhaltens des menschlichen Modells von einem Menschen nicht entschieden werden kann. Dann was?

Nun könnten Sie einwenden, dass die Diagonalisierung nicht anwendbar wäre. Das würde wohl bedeuten, dass es nicht mehr möglich wäre, eine Form der Gödel-Nummerierung mit Rechengeräten, Beweisen oder allem, was wir mit Notation beschreiben, zu verknüpfen, obwohl dies derzeit die Grundlage aller Wissenschaft ist. Mit anderen Worten, wir müssten uns mit Entitäten befassen, Begriffen, die keine schriftliche Repräsentation haben, die keine schriftliche Repräsentation haben können, oder allgemeiner Begriffen ohne syntaktische Repräsentation, ob schriftlich, mündlich oder auf andere Weise.

Dies würde natürlich der Lehre von Johannes widersprechen, dessen allererster Satz lautet: " Am Anfang war das Wort, und das Wort war mit Gott, und das Wort war Gott. " Wort, ist also eine sehr anti-christliche Aussage. Ich beziehe mich natürlich nicht darauf, aber da ich diese Frage zum ersten Mal als metaphysisch betrachte und die Frage nicht zurückgestellt wird, erscheint es selbstverständlich, alle Konsequenzen einschließlich der metaphysischen Konsequenzen zu berücksichtigen.

babou
quelle
Nicht-Christ ist nicht gleich Atheist.
Ubadub
@ubadub Du hast vollkommen recht. Mein Fehler, oder genauer gesagt, meine mangelnde Aufmerksamkeit für einen wichtigen Punkt. Ich habe die Korrektur gemacht. Würdest du wissen, was andere Religionen zu diesem Thema zu sagen haben?
Babou
Mehrere buddhistische Schulen würden die "absolute" Realität als unbeschreiblich einstufen, dh jenseits der sprachlichen Beschreibung, und doch für die Erleuchteten erkennbar. Dies führt zu einer Reihe interessanter philosophischer Fragen, die seit Jahrtausenden im Buddhismus diskutiert werden. Siehe diesen Artikel: bit.ly/2G71tmk für einen Take, obwohl es nicht der einzige ist. Garfield hat eine dialetheistische Lesart des Madhyamaka-Buddhismus, der nicht alle Gelehrten zustimmen (siehe z. B. "Ist Gorampas" Freiheit von konzeptuellen Proliferationen "dialetheistisch?" Von C. Kassor).
Ubadub
8

Betrachten Sie dies aus einer anderen Perspektive.

  • Logik erster Ordnung ist unentscheidbar, dh es gibt keine Entscheidungsprozedur, die bestimmt, ob beliebige Formeln logisch gültig sind. (Die Menge der wahren Formeln erster Ordnung ist jedoch halbentscheidbar . Wenn also eine Formel wahr ist, ist es möglich, einen Beweis mit einem Algorithmus zu finden.)
  • Beweisassistenten helfen, Theoreme in der Logik erster Ordnung (oder sogar höherer Ordnung) zu beweisen. Der Proof-Assistent stellt sicher, dass der Proof korrekt ausgeführt wird, und kann in einigen Fällen sogar zur Lösung beitragen. Menschliche Interaktion ist jedoch erforderlich, um den Proof-Assistenten zur richtigen Antwort zu führen.

Proof-Assistenten könnten zum Nachweis der Eigenschaften einzelner Turing-Maschinen eingesetzt werden.

Dave Clarke
quelle
3

Carl Mummerts Kommentar hat es geschafft.

  1. Mein Verständnis (korrigiere mich, wenn ich falsch liege) der Church-Turing-These ist die Idee, dass alles, was berechnet werden kann, von einer Turing-Maschine berechnet werden kann.

  2. Und wenn eine Turing-Maschine berechnen könnte, ob eine andere Turing-Maschine an einer Eingabe anhält oder nicht (Halteproblem), könnten Sie auch berechnen, ob eine andere Turing-Maschine an einer bestimmten Eingabe nicht anhält (tauschen Sie einfach Ja gegen Nein und Nein denn ja!) - bezeichnend, weil man dann diese Turingmaschine für sich selbst füttern könnte - würde sie sich nicht am Eingang aufhalten? Wenn ja (nicht anhalten), dann nein (anhalten ??). Wenn nein, dann ja. Wenn ja, dann nein. Wenn nein, dann ... hmmm.

2. zeigt also, dass es für eine Turing-Maschine unmöglich ist, das Halteproblem zu lösen. Aber ich glaube nicht, dass es derzeit eindeutige Beweise gibt, die 1. widersprechen. Jedes bekannte Rechenmodell kann noch so viel lösen (entscheiden), wie eine Turing-Maschine kann.

Die Beweislast scheint bei der Person zu liegen, die ein neues Rechenmodell entwickelt, das leistungsstärker ist (dh mehr Probleme entscheiden kann) als die klassische Turing-Maschine.

Übrigens, einige großartige Vorträge dazu finden Sie hier .

Bingo
quelle
3

Es gibt keinen Hinweis darauf, dass das menschliche Gehirn mehr als eine Turing-Maschine ist. Tatsächlich scheint es, dass das gesamte Universum auf einer (ausreichend großen) Turing-Maschine simuliert werden kann.

Menschen sind "schlau", weil intelligente Algorithmen geschickt in Neuronen geschrieben sind, sodass Informatiker sie nicht stehlen oder effizient implementieren können. So clever diese Algorithmen auch sind, sie können das Problem des Anhaltens höchstwahrscheinlich nicht zuverlässig lösen.

ithisa
quelle
"Es scheint, als könnte das gesamte Universum simuliert werden" - nein, das kann es nicht, denn das Ungewissheitsprinzip bedeutet, dass wir den Anfangszustand nicht genau genug herausfinden können, um dies zu tun. Wir können simulieren ein , indem sie willkürliche Entscheidungen über den Anfangszustand Universum, aber das ist nicht unbedingt eine Simulation des Universums.
Periata Breatta
1
Es gibt auch keine Beweise dafür, dass alle Gedanken auf Beweisen beruhen. Es ist eine eindeutige Möglichkeit, dass das Wissen dem Beweis überlegen ist und dass das Wissen auf der Grundlage von Beweisen eine viel geringere geistige Fähigkeit ist als das Wissen direkt auf eine Weise, die für den Beweis nicht empfänglich ist. Muss alles Wissen auf Beweisen beruhen? Wie wäre es, neues Wissen direkt zu schaffen?
Wildcard
1
Ein Zitat aus dem Madeleine L'Engle-Buch "Many Waters" bringt es viel prägnanter auf den Punkt, auch wenn es sich lediglich um eine Möglichkeit und nicht um eine sachliche Aussage handelt: "Man muss glauben, dass man einige Dinge sieht." Wenn Sie in die Erkenntnistheorie einsteigen und davon ausgehen, dass nichts existiert, ohne dass dies nachgewiesen ist, schränken Sie den potenziellen Wissensumfang willkürlich ein.
Wildcard
Für den Universumsteil benötigen Sie ein Quantum, z. B. en.wikipedia.org/wiki/…
Fizz
2

Kurz gesagt: NEIN

Es gibt Turingmaschinen für die wir (noch) nicht wissen, ob diese Maschinen Halt machen ( Collatz Conjecture in Beispiel).

Bis wir einen Weg finden, alle Turingmaschinen aufzulisten, für die wir keinen Haltbarkeitsnachweis haben, und bis wir keinen Weg finden, den Haltbarkeitsnachweis für diese Maschinen zu erbringen, sind wir nicht besser als eine Turingmaschine (If Ich bin richtig, jemand hat bereits bewiesen, dass wir nicht alles beweisen können, was darauf hinweist, dass wir so begrenzt sind wie Turing Machines. Oh, warte, wir können nicht alle diese Maschinen aufzählen, da wir nur einen begrenzten Speicher und eine begrenzte Lebensdauer haben.

Wie auch immer du fragst, antwortet selbst:

Sie fragen, ob Menschen in der Lage sind, zu "entscheiden", aber die Entscheidung selbst ist als Algorithmus definiert, oder wir führen einen Algorithmus in unseren Köpfen aus und kommen zu einer korrekten Schlussfolgerung (oder zu keiner Schlussfolgerung: offene Probleme) oder Wir raten nur.

In der Berechnungstheorie geht es um:

  • Angenommen, es gibt einen Black-Box-Algorithmus (Oracle), der bestimmte Fragen mit Ja oder Nein beantworten kann
  • Sie können es dann verwenden, um unbeantwortete Fragen zu beantworten, indem Sie einen anderen Algorithmus erstellen, der es verwendet
  • Damit endet man mit einem Widerspruch

Das bedeutet, solange Sie ein System haben, das eine Nooder eine YesAntwort wünscht , ist das Oracle nicht mit diesem System kompatibel, sodass Oracles möglicherweise tatsächlich vorhanden ist, aber wir haben keine Möglichkeit, ihre Ergebnisse zu kommunizieren , denn wenn wir in der Lage sind, ihre Ergebnisse dann zu kommunizieren Wir haben irgendwo einen Widerspruch.

Angenommen, die Quantenmechanik besteht aus vielen kleinen Orakeln, dann können Sie deren Ergebnisse nicht mitteilen, da Sie beim Lesen des Status eines Partikels auch den Status dieses Partikels ändern.

Ich hatte die Antwort, aber ich habe es gelesen ..

Tatsächlich können wir alles beweisen, wenn wir von einer falschen Hypotesis ausgehen. Wir können also beweisen, dass ein Algorithmus anhält, aber wir können auch beweisen, dass ein Algorithmus nicht anhält, das kann interessant sein, aber es ist nutzlos, da ein widersprüchliches Ergebnis (Sie wollen ein Yesoder eine NoAntwort) nicht das ist, was Sie wollen.

Spielentwickler
quelle
Warum Abstimmungen? Die Tatsache, dass es nicht möglich ist, das Ergebnis eines Orakels zu kommunizieren, ist ein sehr tiefer und interessanter Punkt, der auch die Frage beantwortet.
GameDeveloper
Aber glauben Sie nicht, dass Menschen irgendwann Probleme wie Collatz Conjecture
DollarAkshay
1

Wie bei der Antwort von DCs (und um es etwas zu erweitern) gibt es einen starken Sinn, in dem diese Frage (die Kombination von Mensch und Computer bei der Suche nach Sonderfalllösungen für das Stopp-Problem) mit dem Bereich ATP, der automatisierten Theoremprüfung und verknüpft ist die eng verwandten computergestützten Beweise . es ist auch seit langem bekannt, dass es in der Curry-Howard-Korrespondenz eine starke Korrespondenz zwischen Programmen und Beweisen gibt . auch hiermit verwandt / vergleichbar ist der Nachweis der Programmbeendigung (z. B. über Schleifeninvarianten oder Schleifenvarianten ). in der Tat gibt es einen tiefen Sinn, in dem alleIn der Mathematik geht es um dieses Problem, da praktisch alle mathematischen Aussagen in Fragen zu bestimmten Programmen auf TMs konvertiert werden können, die anhalten oder nicht anhalten. siehe zB [2] für einige weitere Infos & viele weitere Referenzen zu ATP etc.

[1] ist ein halbberühmtes Buch zu diesem Thema, das die Frage im Detail untersucht und sie mit der Möglichkeit künstlicher Intelligenz in Verbindung bringt. Kurz gesagt, Penrose ist der Meinung, dass wahre KI unmöglich sein muss, da Menschen Beweise für Unentscheidbarkeit vorlegen können, wie zum Beispiel das Problem des Stillstands von Turings oder den Beweis der Unvollständigkeit von Godels, während Computer aufgrund derselben Phänomene nicht möglich sind.

[1] Des Kaisers neuer Geist von Penrose

[2] abenteuer und aufregungen in ATM , vzn

vzn
quelle
1
Ich verstehe nicht, wie jemand diese Antwort ablehnen kann, da sie eine Menge interessantes Material verknüpft. +1 und +100, wenn ich nur könnte.
GameDeveloper
-1

Moderne Supercomputersysteme können mit Sicherheit das Verhalten mindestens eines Atoms simulieren. Wenn einzelne Atome simuliert werden können, kann man auch den menschlichen Geist simulieren, indem man ein ausreichend großes Computersystem für die Simulation der einzelnen Atome aufbaut. Ich denke jedoch, dass dies alleine nicht ausreichen würde. Sie würden auch eine Entropiequelle benötigen, um echte Zufallszahlen für die Simulation des menschlichen Geistes zu erhalten. Die beste Entropiequelle wäre wahrscheinlich der radioaktive Zerfall oder so etwas. Was bedeutet das?

Ich denke, dass der menschliche Geist stärker ist als eine Turing-Maschine, weil ein TM deterministisch ist. Auf einer Turing-Maschine können Sie keine echte Zufälligkeit simulieren. (Zumindest ist dies der Eindruck, den ich aus der folgenden Diskussion gewonnen habe

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

Ich denke jedoch, dass eine Turing-Maschine, die an eine echte Entropiequelle angeschlossen ist, in der Lage ist, einen menschlichen Geist zu simulieren.

Wenn man auch die Zufälligkeit der Umwelt berücksichtigt, die mit dem menschlichen Verstand interagiert (z. B. das Essen, das wir essen, wie der Schlaf, das Gehen, im Grunde unser Leben leben), dann denke ich sicher, dass ein TM mit Entropie dafür nötig ist die Simulation des menschlichen Geistes. Vergessen Sie nicht, dass der menschliche Geist auch ständig Hintergrundstrahlung ausgesetzt ist, die auch unvorhersehbar mit den Molekülen in unserem Gehirn interagieren kann. Aber ich denke, selbst wenn wir eine vollständig "isolierte" Umgebung betrachten (ist das überhaupt möglich? Denn das Folgende scheint darauf hinzudeuten, dass dies möglicherweise nicht möglich ist: http://hps.org/publicinformation/ate/faqs/faqradbods.html) - im Grunde genommen ein "Gehirn im Glas" - Szenario, man würde wahrscheinlich noch wirklich zufällige Vorgänge bekommen, die irgendwo im menschlichen Gehirn auftreten würden. Ich bin sicher, dass ein Biologe diesen Teil der Frage regeln könnte? Vergessen Sie auch nicht, dass ein Mensch in gewisser Weise auch Teil seiner Umwelt ist:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

Vielleicht beeinflussen einige dieser Bakterien auch das innere Funktionieren des menschlichen Gehirns auf irgendeine Weise, und die Zusammensetzung dieser Bakterien kann sich im Laufe des Lebens eines Menschen ändern (auch innerhalb gewisser Grenzen, nehme ich an?). Die Frage ist, ob das Verhalten dieser Bakterien innerhalb bestimmter Grenzen zufällig ist. Wenn mindestens ein Prozess in mindestens einem dieser Organismen wirklich zufällig ist und auch indirekt das menschliche Gehirn beeinflusst, dann würde man eine TM mit einer Entropiequelle benötigen, um einen menschlichen Geist zu simulieren.

Um die ursprüngliche Frage zu beantworten:

Kann ein "Mensch" (wie in der Frage definiert) das Halteproblem lösen? Ja, wenn es das Stopp-Problem für alle deterministischen TMs ist und nein, wenn es für alle TMs ist, die an eine Entropiequelle gebunden sind.

Christopher Schmidt
quelle
2
Dies scheint sehr spekulativ. Im Wesentlichen sagen Sie, dass der menschliche Verstand Zufälligkeit beinhaltet, was bedeutet, dass es sich nicht um eine Turing-Maschine handelt, was bedeutet, dass es möglicherweise in der Lage ist, das Stopp-Problem zu entscheiden?
David Richerby
Es ist wahrscheinlich richtig, dass ein Computer simulieren kann, was wir über Atome wissen. Aber woher wissen Sie, dass wir nur wissen müssen, was wir wissen? Dann ist Zufälligkeit schön: Wenn Sie lange genug warten, finden Sie die richtige Antwort ... unter vielen anderen. Benutze einfach genug Affen für lange genug, oder sieh dir das richtige Buch in der Bibliothek von Babel an. Aber die richtige Antwort zu bekommen ist nicht alles: Woher weißt du, dass es die richtige Antwort ist?
Babou
Nicht deterministische Turingmaschinen sind nicht leistungsfähiger als Turingmaschinen. Zufälligkeit ist nicht genug, um Turing Machines überlegen zu sein. Siehe meine Antwort
GameDeveloper
-2

Jedes menschliche Denken verbindet einzelne Probleme mit persönlicher Erfahrung. Wir können uns davon überzeugen, dass wir ein Problem ausreichend gelöst haben, um es zum Stillstand zu bringen, aber wir wissen nie genau, ob ein Computer im algorithmischen Sinne eine Lösung finden würde. Sei still und achte auf deinen eigenen Verstand. 99,9% der Nachrichten, die in unseren neuronalen Schaltkreisen gesendet werden, haben nichts mit einer logischen Darstellung der Welt zu tun. Stattdessen haben wir es mit Bauchgefühlen, Sinnesdaten und einer Flut von Erinnerungen, Assoziationen und Einstellungen zu tun, die sich ständig ändern. Deshalb haben wir wissenschaftliche Methoden.

Steve
quelle
Ich denke, Sie haben die Frage falsch verstanden. Die Frage ist, ob Menschen entscheiden können, ob eine gegebene Turing-Maschine anhält, was eigentlich nichts damit zu tun hat, "ein Problem ausreichend zu lösen, um anzuhalten". Wollen Sie damit sagen, dass wir uns "ausreichend davon überzeugen" können, dass die Maschine anhält?
Tom van der Zanden