Entscheidbarkeit des fraktalen Labyrinths

17

Ein fraktales Labyrinth ist ein Labyrinth, das Kopien von sich selbst enthält. ZB der folgende von Mark JP Wolf aus diesem Artikel :

Beginnen Sie am MINUS und begeben Sie sich zum PLUS. Wenn Sie eine kleinere Kopie des Labyrinths eingeben, achten Sie darauf, den Buchstabennamen dieser Kopie aufzuzeichnen, da Sie diese Kopie auf dem Weg nach draußen belassen müssen. Sie müssen jede verschachtelte Kopie des Labyrinths, in das Sie eingetreten sind, in der umgekehrten Reihenfolge verlassen, in der Sie sie eingegeben haben (z. B. A, B, C, C, B, A). Stellen Sie es sich als eine Reihe verschachtelter Boxen vor. Wenn die verschachtelte Kopie keinen Exit-Pfad mehr aufweist, ist eine Sackgasse erreicht. Farbe wurde hinzugefügt, um die Wege klarer zu machen, aber es ist nur dekorativ. Fraktale Labyrinth

Wenn eine Lösung vorhanden ist, sollte die Breitensuche eine Lösung finden. Angenommen, es gibt keine Lösung für das Labyrinth - dann würde unser Suchprogramm für immer tiefer und tiefer gehen.

Meine Frage ist: Wie können wir angesichts eines fraktalen Labyrinths feststellen, ob es eine Lösung gibt oder nicht?

Oder gibt es für ein fraktales Labyrinth einer bestimmten Größe (Anzahl der Ein- / Ausgaben pro Kopie) eine Grenze für die Länge der kürzesten Lösung? (Wenn es eine solche Grenze gäbe, könnten wir nur so tief suchen)

Nick Alger
quelle
Nach dem Lesen der FAQ glaube ich nicht, dass dies gehört. Es ist wahrscheinlich keine Frage der theoretischen Informatik auf Forschungsniveau. Tut mir leid, an der falschen Stelle zu posten. Könnte jemand das richtige Forum empfehlen, um diese Frage zu stellen und / oder dorthin zu verschieben?
Nick Alger
Ich habe darüber nachgedacht, auf math.stackexchange zu posten, seit ich dort teilnehme, aber es schien ein bisschen zu algorithmisch. Ich wusste nicht, dass es einen Stapelaustausch in der Informatik gibt. Wenn die Moderatoren es an einen dieser Orte verschieben möchten, hätte ich nichts dagegen.
Nick Alger
3
Für mich ist es nicht offensichtlich, dass dies hier nicht zum Thema gehört ... Offensichtlich erhalten nicht zum Thema gehörende Fragen normalerweise mehr Downvotes als Upvotes
Joe
7
Können Sie kein fraktales Labyrinth als Pushdown-Automat darstellen, bei dem der Stapel der Sequenz von Submazes entspricht, in der Sie sich befinden? Dann würde sich die Löslichkeitsfrage in ein Leereproblem für kontextfreie Sprachen verwandeln, das entscheidbar ist.
Peter Shor

Antworten:

8

Ein schneller informeller Algorithmus, um zu beweisen, dass das Problem entscheidbar ist:

  • nehme an, dass es Ein- / Ausgänge I 1 , . . . Ich n ;nI1,...In
  • man erstelle einen Graphen in dem jedes I i , das M I N U S und das P L U S Knoten sind, und ersetze jedes verschachtelte Labyrinth M j durch einen K n -Untergraphen (vollständiger Graph); füge die Kanten zwischen I i , M I N U S , P L U S , M j I k entsprechend dem Labyrinth hinzu; behalte "extern" M j I iM jGIiMINUSPLUSMjKnichich,MichNUS,PLUS,Mjichk Kanten, die sich von den entsprechenden "inneren" KantenIiIkvonMjals vollständiger Untergraph unterscheiden;MjichichMjichkichichichkMj
  • alle Pfade von MINUS nach PLUS in aufzählen (Zyklen vermeiden);G
  • Wenn Sie einen Pfad finden, der eine verschachtelte Kopie nicht durchläuft, ist dies eine Lösung. andernfalls erweitern Sie jede "interne" Durchquerung der verschachtelten Labyrinthe jedes Pfades:Mj

Nehmen wir an, dass ein Pfad in der ersten Zählung ist , dann ist der Pfad eine gültige Lösung IIF gibt es einen Pfad von I iI j und von I kI h im ursprünglichen Labyrinth (Grafik G ).MichNUSEINichichEINichjBichkBichhPLUSichichichjichkichhG

So müssen wir erweitern die und B I kB I h Traversierungen Aufzählen alle Pfade von I i bis I k und I k zu I h in G .EINichichEINichjBichkBichhichichichkichkichhG

Endlosschleifen werden erkannt, wenn wir alle Pfade von bis I k in einer Erweiterung eines Pfads auflisten, der in einer vorherigen Stufe bereits enthalten war . . . M I iM I k. . . für ein Submaze M (es gibt nur n 2 mögliche Erweiterungen).ichichichk...MichichMichk...Mn2

Eine Lösung ist gefunden, wenn wir eine Pfaderweiterung finden, die nur Ein- / Ausgänge ; Das Labyrinth hat keine Lösung, wenn wir die Pfade ohne Schleifen nicht weiter ausbauen können.ichich

Marzio De Biasi
quelle
Beeindruckend! Was für eine clevere Idee. Ich denke, das funktioniert, aber es ist immer noch ein wenig verschwommen in meinem Kopf, deshalb werde ich mir etwas Zeit nehmen, um darüber nachzudenken, bevor ich es akzeptiere.
Nick Alger
Ok yep ziemlich sicher, dass dieser Algorithmus korrekt ist. Wenn Sie Peter Shors obigen Kommentar beachten, frage ich mich, ob Sie dies umkehren könnten, um einen Beweis für das kontextfreie Problem der Entscheidbarkeit der Leere der Sprache zu liefern. Konstruieren Sie für ein gegebenes kontextfreies Sprachleerheitsproblem ein äquivalentes fraktales Labyrinth und wenden Sie dann diesen Algorithmus an.
Nick Alger
@Nick: Ein fraktales Labyrinth entspricht einem reversiblen Pushdown-Automaten. Wenn Sie von einem Zustand S zu einem Zustand T wechseln können, können Sie auch von T zu S wechseln . Es sollte einfach sein zu zeigen, dass fraktale Labyrinthe sind Tatsächlich entspricht dies reversiblen Pushdown-Automaten. Es gibt einen Satz, der besagt, dass reversible Turingmaschinen (bis auf Polynomfaktoren) die gleiche Leistung haben wie normale Turingmaschinen. Ich weiß nicht, ob sich jemand zuvor mit reversiblen Pushdown-Automaten befasst hat, daher weiß ich nicht, ob etwas über sie bekannt ist.
Peter Shor
@ Peter: Ich habe diese reversiblen Pushdown-Automaten gefunden , aber die Definition von "reversibel" scheint anders zu sein. (PS Glückwunsch für die einfache und klare Interpretation eines fraktalen Labyrinths als PDA !!!)
Marzio De Biasi
1
Der obige Algorithmus könnte auf gerichtete Graphen (irreversible fraktale Labyrinthe) ausgedehnt werden, Sie müssten nur mögliche Erweiterungen in Betracht ziehen ( I kI j und I jI k ). 2n2ichkichj ichjichk
Nick Alger
1

Dies ist keine "Antwort" auf meine Frage, sondern ein erweiterter Kommentar, den die Leute hier vielleicht interessant finden.

Ich behaupte, dass es eine natürliche "Analyse-Typ" -Definition für ein Labyrinth und eine Lösung gibt, die sich von der hier verwendeten computerwissenschaftlich-graphentheoretischen Definition unterscheidet. Insbesondere kann es sich um ein fraktales Labyrinth handeln, das unter der Analysedefinition eine "Lösung" enthält, jedoch vom Marizio De Biasi-Algorithmus und der Pushdown-Automatentechnik von Peter Shor für unlösbar erklärt wird.

Definition: Ein Labyrinth ist eine kompakte Teilmenge der Ebene M R 2, die einen Startpunkt und einen Endpunkt s , e M enthält . Eine Lösung ist eine kontinuierliche Funktion f : [ 0 , T ] M , so daß f ( 0 ) = s und f ( T ) = e .MMR2s,eMf:[0,T]Mf(0)=sf(T)=e

Betrachten Sie nun die Hilbert-Kurve :

Hilbert curve GIF aus Wikipedia

Diese Kurve könnte man mit folgendem Diagramm als "fraktales Labyrinth" interpretieren: Bildbeschreibung hier eingeben

P

P=EINPEIN-1BPB-1CPC-1DPD-1

Nun könnten Sie argumentieren, dass dies nicht im Sinne fraktaler Irrgärten ist, da die Hilbert-Kurve das gesamte Quadrat ausfüllt und Sie daher einfach ein gerades Liniensegment vom Anfang bis zum Ende zeichnen könnten. Dieser Einwand kann jedoch leicht außer Kraft gesetzt werden. Verwenden Sie einfach die direkte Einbettung des Hilbert-Kurvendiagramms, wie hier gezeigt:

Bildbeschreibung hier eingeben

Auch dies enthält eine Folge gleichmäßig konvergenter kontinuierlicher Pfade, die vom Anfang bis zum Ende verlaufen, und zwar nach demselben Argument, mit dem die gleichmäßige Konvergenz der Hilbert-Kurve gezeigt wird. Es ist jedoch ein wahres "fraktales Labyrinth" in dem Sinne, dass es nicht den gesamten Raum ausfüllt.

Wir haben also ein fraktales Labyrinth, das durch die analytische Definition lösbar, aber durch die graphentheoretische Definition unlösbar ist.

Wie auch immer, ich bin mir ziemlich sicher, dass meine Logik richtig ist, aber sie scheint mir nicht intuitiv zu sein. Wenn also jemand Licht in diese Sache bringen kann, wäre ich dankbar.

Nick Alger
quelle
Ein naiver Kommentar: Die "Submazes" der Hilbert-Kurve sind kleiner, also funktioniert es in der "kontinuierlichen Welt"; In der "diskreten Welt" werden Sie niemals einen "Exit" -Zug machen, da Sie weiterhin in das erste Submaze eintreten (wie ein endloser Zoom links unten in der Hilbert-Kurve). Es ähnelt den Paradoxen
Marzio De Biasi
2
PS Ich denke, dass es keiner fraktalen Kurve bedarf: Eine einfache horizontale Linie von s nach f mit einem einzigen zentralen Submaze (die eine einzige horizontale Linie mit einem Sub-Submaze-Äcc. Hat) führt zu den gleichen Überlegungen.
Marzio De Biasi
Guter Punkt. Wenn Sie dies mit einer Teilbox mit der Breite 1/2 ganz rechts tun, ist dies nicht nur das Paradoxon von zeno, sondern Sie erhalten genau das Paradoxon von zenos. Nach weiteren Überlegungen sieht es so aus, als ob die kontinuierliche Definition für fraktale Labyrinthe nicht gut geeignet ist, da sie fast jedes fraktale Labyrinth lösbar macht.
Nick Alger
aber es ist gut geeignet für Zen-Labyrinth-Meditation (Google um den Unterschied zwischen einem Labyrinth und Labyrinth in einem Meditationskontext) :-)
Marzio De Biasi