Decidibilidade do labirinto fractal

Um labirinto fractal é um labirinto que contém cópias de si mesmo. Por exemplo, o seguinte de Mark JP Wolf deste artigo :

Comece no MINUS e siga para o PLUS. Ao inserir uma cópia menor do labirinto, certifique-se de registrar o nome da letra dessa cópia, pois você terá que deixar essa cópia na saída. Você deve sair de cada cópia aninhada do labirinto em que entrou, deixando na ordem inversa em que os inseriu (por exemplo: digite A, digite B, digite C, saia C, saia B, saia B, saia A). Pense nisso como uma série de caixas aninhadas. Se não houver caminho de saída saindo da cópia aninhada, você alcançou um beco sem saída. A cor foi adicionada para tornar os caminhos mais claros, mas é apenas decorativa.

Se houver uma solução, a primeira pesquisa de largura deverá encontrar uma solução. No entanto, suponha que não haja solução para o labirinto - então nosso programa de pesquisa será executado para sempre cada vez mais fundo.

Minha pergunta é: dado um labirinto fractal, como podemos determinar se ele tem uma solução ou não?

Ou, alternativamente, para um labirinto fractal de um determinado tamanho (número de entradas / saídas por cópia), existe um limite para o comprimento da solução mais curta? (se houvesse esse limite, poderíamos pesquisar exaustivamente apenas até esse ponto)

Um algoritmo informal rápido para provar que o problema é decidível:

• suponha que há Entrada / Saídas I 1 , . . . Eu n ;$n$$I_1,...I_n$
• construir um gráfico , onde cada eu i , o M I N L S e o P G L S são os nós, e substituir cada aninhada labirinto H j com um K n subgráfico (gráfico completo); adicione as arestas entre I i , M I N U S , P L U S , M j I k de acordo com o labirinto; mantenha "externo" M j I i → M $G$$I_i$$MINUS$$PLUS$$Mj$$K_n$$I_i, MINUS, PLUS, Mj_{I_k}$ arestas distintas das correspondentes arestas "internas"Ii→IkdeMjcomo um subgráfico completo;$Mj_{I_i} \rightarrow Mj_{I_k}$$I_i \rightarrow I_k$$Mj$
• enumere todos os caminhos de MENOS a MAIS em (evitando ciclos);$G$
• se você encontrar um caminho que não atravessa uma cópia aninhada, é uma solução; caso contrário, expanda cada travessia "interna" dos labirintos aninhados de cada caminho:$Mj$

Suponha que um caminho na primeira enumeração seja , então o caminho é uma solução válida se houver um caminho de I i → I j e de I k → I h no labirinto original (gráfico G ).$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$I_i \rightarrow I_j$$I_k \rightarrow I_h$$G$

Portanto, temos de expandir a e B I k → B I h traversals enumerando todos os caminhos de I i a I k e de I k a I h em G .$A_{I_i} \rightarrow A_{I_j}$$B_{I_k} \rightarrow B_{I_h}$$I_i$$I_k$$I_k$$I_h$$G$

Ciclos infinitos são detectados quando estamos enumerar todos os caminhos de a I K em uma expansão de um caminho que numa fase anterior já contido . . . → M I i → M I k → . . . para alguns submaze M (existem apenas N 2 expansões possíveis).$I_i$$I_k$$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$M$$n^2$

A solução é encontrada, se encontrarmos uma expansão caminho que contenha apenas entradas / saídas ; o labirinto não tem solução se não pudermos expandir ainda mais os caminhos sem loops.$I_i$

Esta não é uma "resposta" para minha pergunta, mas um comentário estendido que as pessoas aqui podem achar interessantes.

Afirmo que existe uma definição "tipo de análise" natural de labirinto e solução, e difere da definição de ciência da computação / teoria de grafos que usamos aqui. Em particular, você pode ter um labirinto fractal que possui uma "solução" sob a definição de análise, mas seria declarado insolúvel pelo algoritmo de Marizio De Biasi e pela técnica de autômatos de empilhamento de Peter Shor.

$M$$M \subset \mathbb{R}^2$$s,e \in M$$f:[0,T] \rightarrow M$$f(0)=s$$f(T)=e$

Agora considere a curva de Hilbert :

Pode-se interpretar essa curva como um "labirinto fractal" com o seguinte diagrama:

$P$

$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$

Agora você pode argumentar que isso não está no espírito dos labirintos fractais, já que a curva de Hilbert preenche todo o quadrado e, portanto, você pode simplesmente desenhar um segmento de linha reta do início ao fim. Essa objeção é facilmente anulada - basta usar o diagrama de curva de hilbert incorporado diretamente, como mostrado aqui:

Isso também contém uma sequência de caminhos contínuos uniformemente convergentes que vão do início ao fim, pelo mesmo argumento usado para mostrar a convergência uniforme da curva de Hilbert. No entanto, é um verdadeiro "labirinto fractal" no sentido de que não preenche todo o espaço.

Assim, temos um labirinto fractal que pode ser resolvido pela definição analítica, mas não pode ser resolvido pela definição teórica do gráfico ..!?

De qualquer forma, tenho certeza de que minha lógica está correta, mas parece contra-intuitivo, portanto, se alguém puder lançar alguma luz sobre isso, eu apreciaria.