Gibt es ein nicht Turing-vollständiges Berechnungsmodell, dessen Stopp-Problem nicht zu entscheiden ist?

26

Ich kann mir kein solches Modell vorstellen, vielleicht irgendeine Form von typisierter Lambda-Rechnung? ein elementarer zellularer Automat?

Dies würde Wolframs "Prinzip der rechnerischen Äquivalenz" beinahe widerlegen:

Fast alle Prozesse, die nicht offensichtlich einfach sind, können als Berechnungen von gleicher Komplexität angesehen werden

automata-theory computability turing-machines lambda-calculus universal-computation Diego de Estrada
quelle

Antworten:

18

Sie können leicht künstliche Modelle bauen, die nicht vollständig sind, aber das Halteproblem für sie ist nicht zu entscheiden. Nehmen Sie zB alle TMs, die bei nichts anderem als bleiben .0

In Bezug auf die Aussage:

Sie können eine Aussage, die nicht präzise genug ist, nicht widerlegen. Fast keines der Wörter in der Erklärung ist genau definiert (bitte geben Sie die Definition für sie an, wenn dies nicht der Fall ist).

Kaveh
quelle
mmm, nehmen wir an, ein Modell ist Turing-vollständig, wenn es eine UTM simulieren kann.
Diego de Estrada
1
Ich denke, Wolframs Äquivalenzprinzip ist der Physik näher als der Logik. Logiker scheinen es aus verschiedenen Gründen zu mögen: Es ist nicht genau, es wurde nicht bewiesen, wir können Dinge so arrangieren, dass es falsch ist, usw. Aber tatsächlich weist Wolfram auf seine eigene Weise auf eine sehr interessante Tatsache in Bezug auf die Berechnung hin , wie es "in der Natur" entsteht.
Andrej Bauer
1
Ich weiß nicht, wie man Kirschen pflückt, das Buch scheint mir ziemlich umfassend zu sein, besonders die ganzen Notizen. Gibt es einen a priori Grund, Änderungen von Standarddefinitionen nicht zuzulassen? Sie messen hier mit dem falschen Maßstab. Wolfram rechnet nicht, jedenfalls nicht im herkömmlichen Sinne.
Andrej Bauer
4
@Andrej, mein Hauptproblem ist, dass die Aussage so vage ist, dass ich nicht sehe, wie sie überprüfbare / widerlegbare Vorhersagen treffen kann. Und ja, wenn jemand die Standarddefinitionen ändert, nur um in der Lage zu sein, zu interpretieren, was keine Unterstützung für eine Forderung wäre, dann halte ich dies für problematisch.
Kaveh
4
Die Aussage ist vage, aber was soll's? Es ist keine Logik oder Mathematik. Es ist eine Beobachtung, die durch ein dickes Buch voller Beispiele gestützt wird, dass "Rechensysteme" in der Natur dazu neigen, entweder trivial einfach oder extrem ausgefeilt und einander "äquivalent" zu sein. Anstatt Wolfram dafür zu kritisieren, dass er nicht die Fachsprache Logik und Mathematik spricht, wäre es produktiver zu sehen, dass er einen Punkt hat, und diesen Punkt dann in einem beliebigen Formalismus zu formulieren, den Ihr Herz wünscht. Aber natürlich, wenn Ihr Herz nicht so etwas wünscht, dann werden Sie es nicht tun.
Andrej Bauer
4

Ich bin mir ziemlich sicher, dass das Argument der Diagonalisierung für jedes Berechnungsmodell gilt, das:

  • kann sich selbst als Zeichenfolge darstellen, und
  • kann eine andere Maschine simulieren, wenn die obige Darstellung gegeben ist

Wenn wir ein Modell hätten, das gegen eine der oben genannten Bedingungen verstößt, wäre seine Rechenleistung äußerst begrenzt.

gabgoh
quelle
10
∀x.f(x)≠x
2

Ich bin mir über den genauen Zusammenhang nicht sicher, aber dies scheint mit dem Friedberg-Muchnik-Theorem zu tun zu haben (siehe hier ): Es gibt ein Re-Set, dessen Turing-Grad geringer ist als das Halteproblem. Dieses Ergebnis beantwortete eine einflussreiche Frage von Post und führte zur Einführung der "Prioritätsmethode" in der Berechenbarkeit.

Super0
quelle
-2

Wahrscheinlich. Es gibt viele mathematische Probleme, zu denen wahrscheinlich einige gehören, die unentscheidbar sind, dh die Antwort lautet "Ja", aber es gibt keinen Beweis dafür. Als Kandidat fällt beispielsweise das Collatz 3x + 1-Problem ein. Oder die Frage, ob pi beliebig lange Zeichenketten von aufeinanderfolgenden 9s enthält. Jedes derartige Problem könnte als ein "Rechenmodell" angesehen werden, das vermutlich viel weniger leistungsfähig ist als eine UTM, aber es wäre immer noch unentscheidbar, ob es "anhält" oder ob es "immer anhält".

Warren D. Smith
quelle
Ich denke nicht, dass dieser Ansatz funktionieren könnte. Siehe: Für eine solche feste Aussage gibt es einen Algorithmus, der in endlicher Zeit entscheidet, ob sie "wahr" oder "falsch" ist, auch wenn sie in ZFC nicht entscheidbar ist (siehe: en.wikipedia.org/wiki/Busy_beaver) #Anwendungen ). Wenn Sie andererseits das Problem "Wenn Sie eine Aussage machen, entscheiden Sie, ob es einen Beweis in ZFC gibt" als Berechnungsmodell betrachten, denke ich, dass das Modell Turing-vollständig ist.
Diego de Estrada