Was ist die kleinste Turingmaschine, bei der nicht bekannt ist, ob sie anhält oder nicht?

31

Ich weiß, dass das Problem des Anhaltens im Allgemeinen nicht entschieden werden kann, aber es gibt einige Turing-Maschinen, die offensichtlich anhalten, und andere, die dies offensichtlich nicht tun. Was ist von allen möglichen Turingmaschinen die kleinste, bei der niemand einen Beweis hat, ob sie anhält oder nicht?

halting-problem Aaron
quelle

10

Die Antwort hängt von den Besonderheiten des Maschinenmodells ab (Anzahl der Symbole usw.). Laut Wikipedia-Artikel über Busy Beaver gibt es eine 5-Sate-Maschine mit 2 Symbolen, bei der nicht bekannt ist, ob sie anhält oder nicht.

Kaveh

1

Beachten Sie, dass es bei Aarons Frage nicht um die Entscheidbarkeit einer bestimmten Sprache geht, sondern um die Existenz eines Beweises, dass eine bestimmte Turing-Maschine anhält. Für jede Turing-Maschine ist "ihr" Anhalteproblem (ob diese Maschine bei der Leereingabe anhält) "entscheidbar": Es ist entweder "Ja" oder "Nein", und beide Sprachen {Ja} und {Nein} sind entscheidbar. Dies unterscheidet sich stark davon, ob man einen Beweis dafür hat, dass die Maschine anhält oder nicht. Aaron, wenn du meinst "Was ist das kleinste

so dass die Sprache

auf

unentscheidbar ist", kannst du bitte deine Frage bearbeiten?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Michaël Cadilhac

1

„Bei einer Maschine @ MichaëlCadilhac Das Halteproblem in der Regel als, interpretiert

und eine Eingabe

, tut

halt für die Eingabe

?“ nicht „eine Maschine

, tut

halt für alle Eingänge?“

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

David Richerby

@DavidRicherby: Für mich ist das Problem beim Anhalten die Sprache der Maschine (Codes), die bei der Leereingabe anhalten. Wenn es hier nicht die beabsichtigte Bedeutung ist, denke ich, sollte es spezifiziert werden, um mögliche (ok, meine) Verwirrung zu zerstreuen.

Michaël Cadilhac

Es gibt mehrere Möglichkeiten, das Problem zu untersuchen, die gültig und miteinander verknüpft sind, und die Unterscheidung ist in der Tat subtil, was der Fragesteller nicht getan hat.

vzn

38

Die größten Turingmaschinen, bei denen das Stillstandsproblem entscheidend ist, sind:

(wobei ist die Menge der Turing Maschinen mit Zuständen und Symbolen). $TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

Die Entscheidbarkeit von und liegt an der Grenze und ist schwierig zu bestimmen, da sie von der Collatz-Vermutung abhängt, die ein offenes Problem darstellt. $TM(2,4)$ $TM(3,3)$

Siehe auch meine Antwort auf cstheory über Collatz-ähnliche Turingmaschinen und " Small Turing machines and generalized busy beaver competition " von P. Michel (2004) (in der vermutet wird, dass ebenfalls entscheidbar ist). $TM(4,2)$

Kaveh Kommentar und Mohammad Antwort richtig ist, so für eine formale Definition der Standard / Nicht-Standard - Turing - Maschinen in dieser Art von Ergebnissen verwendet sehen Turlough Neary und Damien Woods arbeitet auf kleine universellen Turing - Maschinen, zum Beispiel der Komplexität der kleinen universellen Turing - Maschinen: eine Umfrage (Regel 110 TMs sind schwach universell).

Marzio De Biasi
quelle

2

Ist das Halteproblem für einen bestimmten Satz von Turing-Maschinen nicht immer entscheidbar? Da es in

nur begrenzt viele Maschinen gibt , muss es möglich sein, eine Nachschlagetabelle zu erstellen, in der korrekt angegeben ist, welche Maschinen anhalten und welche nicht, und daher muss es eine Turing-Maschine geben, die diese Nachschlagetabelle verwendet Tabelle, um die Frage richtig zu beantworten.

T M (4, 2)

$TM(4, 2)$

Tanner Swett

2

@TannerSwett: hier betrachten wir das Anhalten Satz

oder, mit anderen Worten, für die Maschinen Turing

entscheidbar ist (siehe Michel Papier).

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

Marzio De Biasi

32

Ich möchte hinzufügen, dass es einige Turing-Maschinen gibt, bei denen das Halting-Problem unabhängig von ZFC ist.

Nehmen Sie zum Beispiel eine Turing-Maschine, die in ZFC nach einem Widerspruchsbeweis sucht. Wenn ZFC dann konsistent ist, wird es nicht aufhören, aber Sie können es in ZFC nicht beweisen (wegen Gödels zweitem Unvollständigkeitssatz).

Es geht also nicht nur darum, noch keinen Beweis gefunden zu haben, manchmal gibt es sogar keine Beweise.

Denis
quelle

ZFC? Was bedeutet ZFC? Ich kann es einfach nicht aus dem Kontext herausfinden.

Acapulco

7

@Acapulco lmgtfy.com/?q=zfc&l=1

Sasho Nikolov

Lol! okay. Ich habe mich gefreut. Touchè. Ich hätte nicht gedacht, dass es Initialen sind, die sich unmittelbar und eindeutig auf dieses Thema beziehen. Auf jeden Fall tut es meiner Meinung nach nicht weh, eine mit freundlicher Genehmigung erstellte "ZFC (Zermelo-Fraenkel-Mengen-Theorie)" -Klärung hinzuzufügen, auch um Unklarheiten zu vermeiden, falls es solche gibt? :)

Acapulco

16

@Acapulco finden Sie Tour und Hilfe . Jeder theoretische Informatiker würde wissen, wofür ZFC steht, so dass es eigentlich keiner Klärung bedarf.

Kaveh

1

Beachten Sie insbesondere die kürzlich entdeckten

Symbol-Maschinen mit ZFC-unabhängigem Halteproblem, die hier (7918 Zustände), hier und hier (1919 Zustände) erörtert wurden . Die Zahl der Staaten wird mit ziemlicher Sicherheit weiter sinken.

2

$2$

Res

5

Niemand hat einen Beweis, ob die Universal Turing-Maschine anhält oder nicht. In der Tat ist ein solcher Beweis aufgrund der Unentscheidbarkeit des Halteproblems unmöglich. Die kleinste ist eine universelle Turing- Maschine mit 2 Zuständen und 3 Symbolen , die von Alex Smith gefunden wurde und für die er einen Preis von 25.000 US-Dollar gewann.

Mohammad Al-Turkistany
quelle

4

Beachten Sie jedoch, dass laut der zitierten Wikipedia-Seite der Beweis der Universalität umstritten ist. Dies ist auch nicht das Standardmodell von Turing-Maschinen: Die angeblich universelle Maschine hat keinen Stoppzustand und kann daher keine Maschine simulieren, die anhält, zumindest nicht im Standardsinne dessen, was eine universelle Turing-Maschine tut.

David Richerby

2

@DavidRicherby: Ich denke, dass die schwache -Universalität der Regel 110 durchaus akzeptiert wird: Es werden zwei verschiedene Wörter links und rechts von der Eingabe wiederholt, und die Haltebedingung ist die Erzeugung eines speziellen Segelflugzeugs (wird nur dann generiert, wenn die simulierte Maschine stoppt). Siehe Matthew Cooks "Universalität in elementaren zellulären Automaten".

Marzio De Biasi

-4

Eine ungenau formulierte, aber vernünftige allgemeine Frage, die auf verschiedene technische Arten untersucht werden kann. Es gibt viele "kleine" Maschinen, die an Zuständen / Symbolen gemessen werden, bei denen das Anhalten unbekannt ist, aber keine "kleinste" Maschine ist möglich, es sei denn, man findet eine gerechtfertigte / quantifizierbare Metrik für die Komplexität eines TM, die sowohl Zustände als auch Symbole berücksichtigt (anscheinend) bisher hat noch niemand einen vorgeschlagen).

$x \times y$ $x$ $y$

$x,y$

vzn
quelle

2

Es ist nicht erforderlich, eine Metrik unter Berücksichtigung von Symbolen und Zuständen zu erstellen. Sobald zwei Symbole auf dem Band sind, ist es klar, dass das Problem des Anhaltens für fast alle Zustände unentscheidbar ist - ich erinnere mich, dass es möglich ist, ein universelles TM mit nur fünf Zuständen zu schreiben. Wenn wir die genaue Grenze der Entscheidbarkeit kennen würden, wäre es sicher leicht, diese Grenze in Paaren (# Staaten, # Symbole) zu beschreiben.

David Richerby

In der Tat geht es bei der Suche nach vielbeschäftigten Bibern darum, Beweise dafür zu finden, ob TMs für anfängliche Setups mit einer kleinen Anzahl von Zuständen und Symbolen anhalten. Es gibt lösbare Fälle. Wenn man das "Kleinste" will, muss man eine genaue Metrik erstellen, die "Klein" misst. Der obige Punkt besagt, dass eine Metrik, die nur Zustände oder Symbole umfasst, als irreführend angesehen werden kann, sofern sie die bekannte Grenze darstellt, an der beide beteiligt sind (und Maschinen, von denen nicht bekannt ist, dass sie universell sind). die Unentscheidbarkeit Grenze in dieser Forschung ist es nicht „easy“ in Bezug auf die überhaupt etwas zu geben, das seine grundlegende Natur ist ....

VZN

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

David Richerby

Bisher hat noch niemand eine Metrik vorgeschlagen. Keine wichtige Grenze in diesem Bereich ist "trivial zu beschreiben" und man würde erwarten, dass ein Szenario über Rices thm unmöglich ist. dies scheint einen Mangel an Vertrautheit mit der Forschung und der zitierten Literaturstelle zu zeigen, die an der Auflösbarkeit von Eingaben für Maschinen interessiert sind, die kleiner sind als diejenigen, von denen bekannt ist, dass sie universell sind (und von denen vermutet wird, dass sie nicht universell sind). Ihre Kommentare scheinen sich auf universelle oder nicht universelle Maschinengrenzen zu konzentrieren, was nicht mit den Grenzen der Entscheidbarkeit von Biber identisch ist, die z. B. in den zitierten Quellen (sowohl oben als auch in den von Marzio) untersucht werden.

vzn

x

$x$

y

$y$

x

$x$

y

$y$

Was ist die kleinste Turingmaschine, bei der nicht bekannt ist, ob sie anhält oder nicht?

Antworten: