Das Halteproblem (glaube ich) ist das Problem, einen allgemeinen Algorithmus zu finden, um zu bestimmen, ob ein bestimmtes Programm in einem Computersystem anhält. Es hat sich gezeigt, dass es dafür kein allgemeines Verfahren gibt (glaube ich). Gilt dies für die organisatorischen Fähigkeiten des Geistes? Jedes Informationsmanagementsystem wie der Geist/das Gehirn muss orchestrieren, wann bestimmte Programme „laufen“ oder geändert werden sollen, und wenn es nicht immer sagen kann, wann ein Programm anhalten wird, wie kann sich das System dann selbst organisieren?
Das Halteproblem sagt nichts direkt über den Verstand aus. Es sagt etwas über rekursive Mengen und rekursiv aufzählbare Mengen aus. Eine rekursiv aufzählbare Menge ist eine Menge von ganzen Zahlen, die von einer Turing-Maschine generiert (aufgezählt) werden können. (Wir können eine Turing-Maschine bauen, die jedes Mitglied des Satzes auf sein Band druckt.)
Der Satz von Turing lautet:
bei jeder Codierung von ganzen Zahlen in Rechenmaschinen die Menge von ganzzahligen Paaren
K = { < ich , j > | Programm i hält an, wenn es auf Eingabe j ausgeführt wird }
ist rekursiv aufzählbar, während sein Komplement
nicht(K) = { < ich , j > | Programm i hält nicht an, wenn es auf Eingabe j ausgeführt wird }
ist nicht.
Es sollte nicht überraschen, dass es viele Mengen von ganzen Zahlen (oder ganzzahligen Paaren) gibt, die nicht rekursiv aufzählbar sind. Es gibt nur abzählbar viele ganze Zahlen (und nur abzählbar viele ganzzahlige Paare), also nur abzählbar viele durch die ganzen Zahlen kodierbare Turingmaschinen. Aber die Menge aller Mengen ganzer Zahlen (die Potenzmenge der ganzen Zahlen) ist überabzählbar unendlich. "Die meisten" Mengen von ganzen Zahlen sind also nicht rekursiv aufzählbar.
Turings Beweis erfolgt durch Diagonalisierung und ähnelt dem Paradoxon des Lügners .
Sehen wir uns die Menge doestHaltOnItself = { i | an Programm i hält nicht an, wenn es auf Eingabe i ausgeführt wird }
Können wir eine Turing-Maschine H konstruieren, die anhält und "accept" für alle i in doestHaltOnItself ausgibt und andernfalls (wenn i anhält, wenn es auf i ausgeführt wird ) für immer läuft? Angenommen. Ist H in doestHaltOnItself? Angenommen, H ist in doestHaltOnItself. Wenn dann H am Eingang H ausgeführt wird, hält es nicht an. Aber für alle iin doestHaltOnItself sollte H anhalten und "accept" ausgeben. Also darf H nicht in doestHaltOnItself stehen. Aber das bedeutet, dass wenn H auf sich selbst läuft, es anhält. Aber wenn H auf einem Programm ausgeführt wird, das auf sich selbst anhält, soll es für immer laufen. Auch ein Widerspruch. Unsere Annahme, dass wir H konstruieren könnten, ist also falsch. Beachten Sie, dass doestHaltOnItself im Wesentlichen eine Teilmenge von not(K) ist, also ist not(K) nicht rekursiv aufzählbar.
Der Satz von Turing sagt uns ebenso wie der Satz von Gödel (und das Diagonalisierungsverfahren von Cantor) etwas Tiefes über die Grenzen von Logik, Mengenlehre und Mathematik.
Ob Turings Theorem (oder Gödels Theorem (oder die Kardinalität von Potenzmengen)) uns irgendetwas Interessantes über den menschlichen Verstand sagt, hängt von einer ganzen Reihe anderer Annahmen ab (z. B. ob Sie glauben, dass Bewusstsein von der Fähigkeit abhängt, Mengen aufzuzählen, die es nicht sind rekursiv aufzählbar.)
Ihre Frage bezog sich speziell auf den Zusammenhang zwischen Turings Theorem und "Selbstorganisation". Ich sehe keinen Zusammenhang zwischen der Fähigkeit zur "Selbstorganisation" und der Fähigkeit, Mengen aufzuzählen, die nicht rekursiv aufzählbar sind. Es ist mir nicht einmal klar, dass ein selbstorganisierendes System in der Lage sein muss, alle rekursiv aufzählbaren Mengen aufzulisten (und sicherlich keine der nicht endlichen rekursiv aufzählbaren Mengen).
Mauro ALLEGRANZA
Josef Weissmann
James Kingsberry
Erik Kaplun