Schleift eine niemals stoppende Maschine immer?

22

Eine Turing-Maschine, die mit ihrem Lese- / Schreibkopf auf derselben Zelle des exakt gleichen Bandes in einen zuvor angetroffenen Zustand zurückkehrt, wird in einer Schleife gefangen. Eine solche Maschine hält nicht an.

Kann jemand ein Beispiel für eine ununterbrochene Maschine nennen, die keine Schleife ausführt?

computability turing-machines halting-problem hollow7
quelle

1

Nur eine Anmerkung: Das Band kann auch anders sein: Eine ausreichende (aber nicht notwendige) Bedingung für eine Endlosschleife, wenn das TM in Schritt

in dieselbe Zelle eintritt und in Schritt

in demselben Zustand ist, ist die Bedingung bei Schritt

der Teil des Bandes, den der Kopf zwischen Schritt

und Schritt

ist gleich dem entsprechenden Teil unmittelbar vor der Eingabe von

.

t_{1}

$t_1$

t_{2} > t_{1}

$t_2 > t_1$

t_{2}

$t_2$

t_{1}

$t_1$

t_{2}

$t_2$

t_{1}

$t_1$

Vor

4

Wenn ein TM eine Schleife ausführen müsste, um nicht anzuhalten, könnten Sie das Problem des Anhaltens für TMs ziemlich einfach lösen: Denken Sie an alle vorherigen Konfigurationen und prüfen Sie bei jedem Schritt, ob Sie sich in einer Konfiguration befinden, die Sie gesehen haben vorher, und wenn ja, wissen Sie, dass das Ding nicht anhält (andernfalls, da wir annehmen, dass es eine Schleife ausführen muss, um für immer zu laufen, wird es nicht für immer laufen, dh es wird anhalten, in welchem Fall wir es schließlich tun werden) davon wissen).

Patrick87

Inspiriert durch die Antwort von @Niel de Beaudrap: Eine Turing-Maschine könnte die oeis.org/A014445-Sequenz berechnen und anhalten, wenn sie eine ungerade Zahl erhält. Es könnte oeis.org/A016742 als laufende Summe berechnen und anhalten, wenn die Zahl ungerade ist. Es könnte berechnet werden, x^2wo xZyklen zwischen -100und 100und dem Radfahren mit einem Modulo durchgeführt werden und angehalten werden, wenn das Ergebnis negativ ist. Es könnte berechnen, x%2wo x von null bis unendlich reicht und anhalten, wenn das Ergebnis gleich 2 ist. In der Assemblersprache haben / while / for-Schleifen alle einen bedingten Sprung, aber der bedingte Sprung allein bedeutet wenig.

Leonid

Die Annahme der Frage gilt nur für deterministische Maschinen.

Raphael

15

Betrachten Sie das TM, das den Bandkopf immer nach rechts bewegt und bei jedem Schritt ein spezielles Symbol für ein nicht leeres Band druckt. Dies bedeutet, dass der TM niemals anhält, da er sich immer nach rechts bewegt und einen Zustand niemals wiederholt, da sich der Bandkopf nach k Schritten über der k-ten Zelle der Maschine befindet. Infolgedessen unterscheidet sich jede Konfiguration der Maschine von allen anderen, und die Maschine macht immer eine Schleife.

Wir konnten auch nicht konstruktiv die Existenz solcher Maschinen zeigen. Nehmen wir an, dass jedes TM, das niemals anhält, irgendwann eine Schleife bildet. Dies bedeutet, dass, wenn Sie ein TM an einem String starten , eines der folgenden Ereignisse eintreten kann: $M$ $w$

hält an oder $M$
wiederholt eine Konfiguration. $M$

In diesem Fall wäre das Halteproblem wie folgt zu entscheiden. Wenn ein TM und eine Zeichenfolge , simulieren Sie auf , und schreiben Sie an jedem Punkt den Inhalt des Bandes, den aktuellen Zustand und die aktuelle Bandposition aus. Wenn es sich bei dieser Konfiguration um ein Duplikat handelt, wird die Ausgabe "nicht angehalten". Andernfalls wird "angehalten" ausgegeben , wenn auf anhält. Da eine davon garantiert irgendwann eintritt, wird dieser Prozess immer beendet, sodass wir einen Algorithmus für das Stopp-Problem haben, von dem wir wissen, dass er nicht existiert. $M$ $w$ $M$ $w$ $M$ $w$

Hoffe das hilft!

templatetypedef
quelle

Hah, schlagen Sie zu dieser Bearbeitung. Siehe meinen Kommentar zu der Frage. Ich mag diese Art zu erklären, warum nicht alle nicht stoppenden TMs eine Schleife bilden müssen ... es baut Intuition auf.

Patrick87

@ Patrick87- Sorry, ich habe den Kommentar nicht bemerkt. Ich dachte an das Addendum auf meinem Weg und setzte mich, um es zu betreten, sobald ich zurückkam.

templatetypedef

Kein Problem, Mann ... Ich bin froh, dass du es hinzugefügt hast, da ich denke, dass es eine gute Möglichkeit ist, es zu erklären. Ich habe es nur als Kommentar und nicht als Antwort hinzugefügt, da Sie mich geschlagen haben. : D

Patrick87

Tatsächlich scheint in Bezug auf das Halteproblem, dass zurückgeht und das Band ad infinitum wechselt, das "wahre Problem" zu sein. Diese Leerenläufer, die du entdecken kannst.

Raphael

12

Eine Turing-Maschine, die alle Nachkommastellen von π (oder einen anderen nicht terminierenden Bruch in einer beliebigen Basis) berechnet, hält niemals an und kann nur eine endliche Anzahl von Malen zum Schreiben auf jede Zelle veranlasst werden. Natürlich wäre die Tatsache, dass es keinen Übergang zu einem Stillstand gibt, ein totes Werbegeschenk, aber es ist zumindest ein natürliches Beispiel.

Ein interessanterer (aber auch mehrdeutiger) Fall wäre eine Turing-Maschine, die iterativ die Collatz-Funktion für ihre Eingabe berechnet, endet genau dann, wenn es die ganze Zahl 1 erhält. Die berühmte Collatz-Vermutung

f (n) = {\begin{cases} 3 n + 1, & ob n ist ungerade; \\ n / 2, & ob n ist gerade, \end{cases}

$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$ Ist das für jede Eingabe, wird diese Prozedur eventuell angehalten. Es ist jedoch nicht bekannt, ob dies der Fall ist. Es kann auf zwei verschiedene Arten, im Prinzip versagen: Entweder es kann eine Folge von ganzen Zahlen finden , die sich um Schlaufen (entsprechend der Existenz einer ganzen Zahl n , so dass

für eine Zahl von Zusammensetzungen, wobei n ≤ 1) ist; oder es könnte sein, dass es Ketten von ganzen Zahlen n , f (n) , f (f (n)) gibt

f \circ f \circ \dots f (n) = n

$f \circ f \circ \cdots f(n) = n$ , ... die asymptotisch zur Unendlichkeit auseinander gehen. Wenn Sequenzen der letzteren Art existieren, würde dies bedeuten, dass sich die Turing-Maschine, die ich oben beschrieben habe, nicht wiederholt, da das Band kontinuierlich zu immer größeren Nummern geändert würde.

Niel de Beaudrap
quelle

Ich spiele gerne mit den Ziffern von pi. Ein TM könnte anhalten, wenn das Quadrat einer beliebigen Ziffer pigenau 7 entspricht.

Leonid

@Leonid: Sie könnten sicherlich eine Turing-Maschine in Betracht ziehen, die Eingaben akzeptiert und unter einer Bedingung anhält, die durch diese Eingaben bestimmt wird. Sie können sogar die Bedingungen angeben, unter denen ein Teil der Eingabe angehalten wird. Und Sie könnten, wie Sie beschreiben, eine Eingabe liefern, die eine Einschränkung festlegt, die niemals erfüllt wird.

Niel de Beaudrap

10

Betrachten Sie eine nicht stoppende Turing-Maschine, die den Schreib- / Lesekopf niemals nach links bewegt.

JeffE
quelle

Einige von ihnen schleifen immer noch. </ nitpicking>

Raphael

5

Wenn dies wahr wäre, dann wäre das Halteproblem entscheidbar. Sie würden einfach jedes (Band-, Status-) Paar aufzeichnen, das Sie beim Ausführen der Turing-Maschine gesehen haben, und die Maschine würde entweder anhalten (in diesem Fall stoppt sie offensichtlich), oder Sie sehen ein Paar, das Sie zuvor gesehen haben, in welchem Fall die Maschine hört nicht auf.

Da das Problem des Anhaltens nicht entschieden werden kann, kann dies nicht zutreffen. (Siehe andere Beispiele für Zählerbeispiele.)

Rekursiv-elektronisch
quelle

Was fügt diese Antwort zur Antwort von templatetypedef hinzu ?

Raphael

Ich denke nicht. Tut mir leid, ich habe diese Antwort irgendwie verpasst, als ich meine schrieb.

RecursivelyIronic

Schleift eine niemals stoppende Maschine immer?

Antworten: