Décidabilité du labyrinthe fractal

17

Un labyrinthe fractal est un labyrinthe qui contient des copies de lui-même. Par exemple, le suivant par Mark JP Wolf de cet article :

Commencez au MOINS et dirigez-vous vers le PLUS. Lorsque vous entrez dans une petite copie du labyrinthe, assurez-vous d'enregistrer le nom de la lettre de cette copie, car vous devrez laisser cette copie à la sortie. Vous devez sortir de chaque copie imbriquée du labyrinthe dans lequel vous êtes entré, en laissant dans l'ordre inverse dans lequel vous les avez entrés (par exemple: entrez A, entrez B, entrez C, quittez C, quittez B, quittez A). Considérez-le comme une série de boîtes imbriquées. S'il n'y a pas de chemin de sortie quittant la copie imbriquée, vous avez atteint une impasse. De la couleur a été ajoutée pour rendre les voies plus claires, mais elle n'est que décorative. Labyrinthe fractal

Si une solution existe, la recherche en premier lieu devrait trouver une solution. Cependant, supposons qu'il n'y ait pas de solution au labyrinthe - alors notre programme de recherche fonctionnerait pour toujours de plus en plus profond.

Ma question est: étant donné un labyrinthe fractal, comment pouvons-nous déterminer s'il a une solution ou non?

Ou bien, pour un labyrinthe fractal d'une taille donnée (nombre d'entrées / sorties par copie), existe-t-il une limite sur la longueur de la solution la plus courte? (s'il y avait une telle limite, nous ne pourrions rechercher exaustivement que profondément)

Nick Alger
la source
Après avoir lu la FAQ, je ne pense pas que cela appartienne. Ce n'est probablement pas une question d'informatique théorique au niveau de la recherche. Désolé de poster au mauvais endroit. Quelqu'un pourrait-il recommander le forum approprié pour poser cette question et / ou la déplacer?
Nick Alger
J'ai envisagé de publier sur math.stackexchange depuis que j'y participe, mais cela semblait un peu trop algorithmique. Je ne savais pas qu'il y avait un échange de pile informatique. Si les modérateurs veulent le déplacer vers l'un de ces endroits, cela ne me dérangerait pas.
Nick Alger
3
Il n'est pas évident pour moi que ce soit hors sujet ici ... de toute évidence, les questions hors sujet obtiennent généralement plus de votes négatifs que de votes positifs
Joe
7
Ne pouvez-vous pas représenter un labyrinthe fractal comme un automate déroulant, où la pile correspond à la séquence de sous-Mazes dans laquelle vous vous trouvez? Ensuite, la question de la solubilité se transformerait en problème de vide pour les langages sans contexte, ce qui est décidable.
Peter Shor

Réponses:

8

Un algorithme informel rapide pour prouver que le problème est décidable:

  • supposons qu'il y ait entrées / sorties I 1 , . . . I n ;nI1,...In
  • construire un graphe où chaque I i , les M I N U S et les P L U S sont des nœuds, et remplacer chaque labyrinthe imbriqué M j par un sous-graphe K n (graphe complet); ajouter les bords entre I i , M I N U S , P L U S , M j I k selon le labyrinthe; garder "externe" M j I iM jGIiMjeNUSPLUSMjKnjeje,MjeNUS,PLUS,Mjjek arêtes distinctes des arêtes "internes" correspondantesIiIkdeMjcomme sous-graphe complet;MjjejeMjjekjejejekMj
  • énumérer tous les chemins de MOINS à PLUS en (en évitant les cycles);g
  • si vous trouvez un chemin qui ne traverse pas une copie imbriquée, alors c'est une solution; sinon élargir chaque parcours "interne" des labyrinthes imbriqués de chaque chemin:Mj

Supposons qu'un chemin dans la première énumération soit , alors le chemin est une solution valide si il y a un chemin de I iI j et de I kI h dans le labyrinthe d'origine (graphique G ).MjeNUSUNEjejeUNEjejBjekBjehPLUSjejejejjekjehg

Nous devons donc développer l' et B I kB I h traversals qui énumèrent tous les chemins de I i à I k et de I k à I h dans G .UNEjejeUNEjejBjekBjehjejejekjekjehg

Des boucles infinies sont détectées lorsque nous énumérons tous les chemins de à I k dans une expansion d'un chemin qui, à une étape précédente, était déjà contenu . . . M I iM I k. . . pour certains submaze M (il n'y a que n 2 extensions possibles).jejejek...MjejeMjek...Mn2

Une solution est trouvée si nous trouvons une extension de chemin qui ne contient que des entrées / sorties ; le labyrinthe n'a pas de solution si nous ne pouvons pas élargir davantage les chemins sans boucles.jeje

Marzio De Biasi
la source
Hou la la! Quelle idée intelligente. Je pense que cela fonctionne, mais c'est encore un peu flou dans mon esprit, donc je vais prendre un peu de temps pour réfléchir avant d'accepter.
Nick Alger
Ok ouais je suis sûr que cet algorithme est correct. Notant le commentaire de Peter Shor ci-dessus, je me demande si vous pourriez inverser la tendance pour fournir une preuve du problème de décidabilité de la vacuité du langage sans contexte ..? Pour un problème de vide de langage sans contexte donné, construisez un labyrinthe fractal équivalent, puis appliquez cet algorithme.
Nick Alger
@Nick: Un labyrinthe fractal correspond à un automate de refoulement réversible , où si vous pouvez faire une transition d'un état S à un état T, vous pouvez également faire la transition de T à S. Il devrait être simple de montrer que les labyrinthes fractals sont en fait équivalent à des automates à refoulement réversibles. Un théorème dit que (jusqu'aux facteurs polynomiaux) les machines de Turing réversibles ont la même puissance que les machines de Turing ordinaires. Je ne sais pas si quelqu'un a déjà étudié des automates de refoulement réversibles, donc je ne sais pas si quelque chose est connu à leur sujet.
Peter Shor
@Peter: J'ai trouvé cet automate de refoulement réversible , mais la définition de "réversible" semble différente. (Félicitations PS pour l'interprétation simple et propre d'un labyrinthe fractal en tant que PDA !!!)
Marzio De Biasi
1
L'algorithme ci-dessus pourrait être étendu aux graphes dirigés (labyrinthes fractals irréversibles), vous auriez juste extensions possibles à considérer ( I kI j et I jI k ). 2n2jekjej jejjek
Nick Alger
1

Ce n'est pas une "réponse" à ma question, mais plutôt un commentaire étendu que les gens d'ici pourraient trouver intéressant.

Je prétends qu'il existe une définition naturelle "de type analyse" d'un labyrinthe et d'une solution, et qu'elle diffère de la définition informatique / graphique-théorique que nous avons utilisée ici. En particulier, vous pouvez avoir un labyrinthe fractal qui a une «solution» selon la définition de l'analyse, mais qui serait déclaré insoluble par l'algorithme de Marizio De Biasi et la technique d'automates à refoulement de Peter Shor.

Définition: Un labyrinthe est un sous - ensemble compact du plan M R 2 contenant un point de départ et un point d'extrémité s , e M , respectivement. Une solution est une fonction continue f : [ 0 , T ] M telle que f ( 0 ) = s et f ( T ) = e .MMR2s,eMF:[0,T]MF(0)=sF(T)=e

Considérons maintenant la courbe de Hilbert :

Hilbert courbe gif de wikipedia

On pourrait interpréter cette courbe comme un "labyrinthe fractal" avec le schéma suivant: entrez la description de l'image ici

P

P=UNEPUNE-1BPB-1CPC-1P-1

Maintenant, vous pourriez faire valoir que ce n'est pas dans l'esprit des labyrinthes fractals puisque la courbe de Hilbert remplit tout le carré et donc vous pouvez simplement dessiner un segment de ligne droite du début à la fin. Cependant, cette objection est facilement contournée - utilisez simplement le diagramme de courbe de Hilbert incorporant directement, comme indiqué ici:

entrez la description de l'image ici

Celui-ci contient également une séquence de chemins continus uniformément convergents allant du début à la fin, par le même argument utilisé pour montrer la convergence uniforme de la courbe de Hilbert. Mais c'est un véritable "labyrinthe fractal" dans le sens où il ne remplit pas tout l'espace.

Nous avons donc un labyrinthe fractal qui est résoluble par la définition analytique, mais insoluble par la définition théorique du graphe ..!?

Quoi qu'il en soit, je suis presque sûr que ma logique est correcte, mais cela semble contre-intuitif, donc si quelqu'un peut faire la lumière sur ce point, je l'apprécierais.

Nick Alger
la source
Un commentaire naïf: les "sous-miroirs" de la courbe de Hilbert sont plus petits, donc dans le "monde continu" ça marche; dans le «monde discret», vous ne ferez jamais un mouvement de «sortie» parce que vous continuez à entrer dans le premier sous-labyrinthe (comme un zoom sans fin en bas à gauche de la courbe de Hilbert). Cela ressemble aux paradoxes de Zeno
Marzio De Biasi
2
PS Je pense qu'il n'y a pas besoin d'une courbe fractale: une simple ligne horizontale de s à f avec un seul sous-sous-sol central (qui a une seule ligne horizontale avec un sous-sous-sous-sol ecc. Ecc.) Conduit aux mêmes considérations.
Marzio De Biasi
Bon point. Si vous faites cela avec une sous-boîte de largeur 1/2 placée à l'extrême droite, ce n'est pas juste comme le paradoxe de zeno, vous obtenez exactement le paradoxe de zenos. Après un examen plus approfondi, il semble que la définition continue ne soit pas bien adaptée aux labyrinthes fractals car elle rend presque tous les labyrinthes fractals solubles.
Nick Alger
mais il convient bien à la méditation du labyrinthe zen (Google recherche la différence entre un labyrinthe et un labyrinthe dans un contexte de méditation) :-)
Marzio De Biasi