Decidability of fractal maze

Question

A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:

Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of that copy, as you will have to leave this copy on the way out. You must exit out of each nested copy of the maze that you have entered into, leaving in the reverse order that you entered them in (for example: enter A, enter B, enter C, exit C, exit B, exit A). Think of it as a series of nested boxes. If there is no exit path leaving the nested copy, you have reached a dead end. Color has been added to make the pathways clearer, but it is only decorative.

If a solution exists, breadth-first-search should find a solution. However, suppose there is no solution to the maze - then our search program would run forever going deeper and deeper.

My question is: given a fractal maze, how can we determine if it has a solution or not?

Or alternatively, for a fractal maze of a given size (number of inputs/outputs per copy), is there a bound on the length of the shortest solution? (if there was such a bound, we could exaustively search only that deep)

Answer 1

A quick informal algorithm to prove that the problem is decidable:

• suppose that there are $n$ Input/Outputs $I_1,...I_n$;
• build a graph $G$ where each $I_i$, the $MINUS$ and the $PLUS$ are nodes, and replace each nested maze $Mj$ with a $K_n$ subgraph (complete graph); add the edges between $I_i, MINUS, PLUS, Mj_{I_k}$ according to the maze; keep "extern" $Mj_{I_i} \rightarrow Mj_{I_k}$ edges distinct from the corresponding "internal" edges $I_i \rightarrow I_k$ of $Mj$ as a complete subgraph;
• enumerate all paths from MINUS to PLUS in $G$ (avoiding cycles);
• if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise expand each "internal" traversals of the nested mazes $Mj$ of each path:

Suppose that a path in the first enumeration is $MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$, then the path is a valid solution iif there is a path from $I_i \rightarrow I_j$ and from $I_k \rightarrow I_h$ in the original maze (graph $G$).

So we must expand the $A_{I_i} \rightarrow A_{I_j}$ and $B_{I_k} \rightarrow B_{I_h}$ traversals enumerating all the paths from $I_i$ to $I_k$ and from $I_k$ to $I_h$ in $G$.

Infinite loops are detected when we are enumerating all paths from $I_i$ to $I_k$ in an expansion of a path that in a previous stage already contained $... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$ for some submaze $M$ (there are only $n^2$ possible expansions).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$; the maze has no solution if we cannot further expand the paths without loops.

Answer 2

This is not an "answer" to my question, but rather an extended comment that people here might find interesting.

I claim that there is a natural "analysis-type" definition of a maze and a solution, and it differs from the computer-science/graph-theoretic definition we've used here. In particular, you can have a fractal maze that has a "solution" under the analysis definition, but would be declared unsolvable by Marizio De Biasi's algorithm and Peter Shor's pushdown automata technique.

Definition: A maze $M$ is a compact subset of the plane $M \subset \mathbb{R}^2$ containing a start point and an endpoint $s,e \in M$, respectively. A solution is a continuous function $f:[0,T] \rightarrow M$ such that $f(0)=s$ and $f(T)=e$.

Now consider the the Hilbert Curve:

One could interpret this curve as a "fractal maze" with the following diagram:

Since the Hilbert Curve iterations converge uniformly, that uniform limit is a continuous path that solves the maze in the analytic sense. It's as if you were able to do the following recursively defined infinite set of moves $P$:

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

Now you might argue that this is not in the spirit of fractal mazes since the Hilbert curve fills the entire square and therefore you could just draw a straight line segment from the start to the finish. This objection is easily overridden though - simply use the hilbert curve diagram embedding directly, as shown here:

This too contains a sequence of uniformly convergent continuous paths going from the start to the finish, by the same argument used to show the uniform convergence of the Hilbert curve. However it is a true "fractal maze" in the sense that it does not fill the whole space.

Thus we have a fractal maze that is solvable by the analytic definition, but unsolvable by the graph theoretic definition..!?

Anyways, I'm pretty sure my logic is correct, but it seems counterintuitive so if anyone can shed some light on this I would appreciate it.