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

<p>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.</p>

<p><strong>Definition:</strong> A <em>maze</em> $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 <em>solution</em> is a continuous function $f:[0,T] \rightarrow M$ such that $f(0)=s$ and $f(T)=e$.</p>

<p>Now consider the the <a href="http://en.wikipedia.org/wiki/Hilbert_curve" rel="nofollow noreferrer">Hilbert Curve</a>:</p>

<p><img src="https://i.sstatic.net/aYbwi.gif" alt="Hilbert curve gif from wikipedia"></p>

<p>One could interpret this curve as a "fractal maze" with the following diagram:
<img src="https://i.sstatic.net/N9IEe.png" alt="enter image description here"></p>

<p>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>

<p>$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$</p>

<p>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:</p>

<p><img src="https://i.sstatic.net/tLcz4.png" alt="enter image description here"></p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-05-09T11:03:10.157Z
A naive comment: the "submazes" of the Hilbert curve are smaller, so in the "continuous world" it works; in the "discrete world" you'll never make an "exit" move because you continue to enter the first submaze (like an endless zoom on the bottom-left of the Hilbert curve). It resembles the [Zeno's paradoxes](http://en.wikipedia.org/wiki/Zeno%27s_paradoxes)
Marzio De Biasi
CC BY-SA 3.0
2012-05-09T11:10:56.123Z
P.S. I think that there is no need of a fractal curve: a simple horizontal line from s to f with a single central submaze (which has a single horizontal line with a sub-submaze ecc. ecc.) leads to the same considerations.
Marzio De Biasi
CC BY-SA 3.0
2012-05-09T18:23:42.060Z
Good point. If you do that with a sub-box of width 1/2 placed on the far right, it's not just like zeno's paradox, you get exactly zenos paradox. After further consideration it looks like the continuous definition isn't well suited for fractal mazes since it makes almost every fractal maze solvable.
Nick Alger
CC BY-SA 3.0
2012-05-09T21:26:30.257Z
but it is well suited for Zen labyrinth meditation (Google around for the difference between a labyrinth and maze in a meditation context) :-)
Marzio De Biasi
CC BY-SA 3.0
2012-05-08T22:13:27.333Z
2012-05-08T22:13:27.333Z
Nick Alger
<p>A quick informal algorithm to prove that the problem is decidable:</p>

<ul>
<li>suppose that there are $n$ Input/Outputs $I_1,...I_n$;</li>
<li>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;</li>
<li>enumerate all paths from MINUS to PLUS in $G$ (avoiding cycles);</li>
<li>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:</li>
</ul>

<p>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$).</p>

<p>So we must <em>expand</em> 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$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-09T14:12:49.077Z
Wow! What a clever idea. I think this works but it's still a little fuzzy in my mind, so I'm going to take a bit of time to mull it over before accepting.
Nick Alger
CC BY-SA 3.0
2012-04-10T02:52:13.803Z
Ok yep pretty sure this algorithm is correct. Noting Peter Shor's comment above, I wonder if you could turn this around to provide a proof for the context-free language emptiness decidability problem..? For a given context free language emptiness problem, construct an equivalent fractal maze, then apply this algorithm.
Nick Alger
CC BY-SA 3.0
2012-04-10T14:29:29.863Z
@Nick: A fractal maze corresponds to a *reversible* pushdown automaton, where if you can make a transition from a state S to a state T, you can also make the transition from T to S. It should be straightforward to show that fractal mazes are in fact equivalent to reversible pushdown automata. There is a theorem saying that (up to polynomial factors) reversible Turing machines have the same power as regular Turing machines. I don't know if anybody has looked into reversible pushdown automata before, so I don't know whether anything is known about them.
Peter Shor 
CC BY-SA 3.0
2012-04-10T15:54:22.740Z
@Peter: I found this [Reversible Pushdown Automata](http://www.springerlink.com/content/k653257805836718/), but the definition of "reversible" seems different. (P.S. congratulations for the simple and clean interpretation of a fractal maze as a PDA!!!)
Marzio De Biasi
CC BY-SA 3.0
2012-04-10T16:50:14.027Z
@Marzio: nice reference. I suppose then that to avoid confusion, the things corresponding to fractal mazes should be called *symmetric* pushdown automata, in analogy with SL (Symmetric Logspace).
Peter Shor 
CC BY-SA 3.0
2012-04-10T17:02:40.053Z
The above algorithm could be extended to directed graphs (irreversibe fractal mazes), you would just have $2n^2$ possible expansions to consider ($I_k \rightarrow I_j$ *and* $I_j \rightarrow I_k$).
Nick Alger
CC BY-SA 3.0
2012-04-09T12:52:55.237Z
2012-04-09T13:04:11.820Z
2012-04-09T13:04:11.820Z
Marzio De Biasi
<p>A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from <a href="http://www.maa.org/editorial/mathgames/mathgames_11_24_03.html" rel="noreferrer">this article</a>:</p>

<blockquote>
  <p>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.
  <img src="https://i.sstatic.net/hxh62.gif" alt="Fractal Maze"></p>
</blockquote>

<p>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. </p>

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

<p>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)</p>

CC BY-SA 3.0
2012-04-08T06:47:47.670Z
After reading the FAQ I do not believe this belongs. It's probably not a reasearch-level theoretical computer science question. Sorry to post in the wrong place. Could someone recommend the proper forum to ask this question and/or move it there?
Nick Alger
CC BY-SA 3.0
2012-04-08T07:52:39.023Z
[math.se], [cs.se].
Kaveh
CC BY-SA 3.0
2012-04-08T08:08:41.250Z
I considered posting on math.stackexchange since I participate there, but it seemed a little too algorithm-y. I didn't know that there is a computer science stack exchange. If the moderators want to move it to either of those places I wouldn't mind.
Nick Alger
CC BY-SA 3.0
2012-04-09T06:10:29.240Z
It's not obvious to me that this is off-topic here... obviously off-topic questions usually get more downvotes than upvotes
Joe
CC BY-SA 3.0
2012-04-09T17:22:51.780Z
Can't you represent any fractal maze as a pushdown automaton, where the stack corresponds to the sequence of submazes that you're in? Then the solubility question would turn into the emptiness problem for context-free languages, which is decidable.
Peter Shor 
<computability><fractals>
Decidability of fractal maze
Nick Alger
# Decidability of fractal maze

(Asked by: username_0 on 2012-04-08)

A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from [this article](http://www.maa.org/editorial/mathgames/mathgames_11_24_03.html):

> 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.
> ![Fractal Maze](https://i.sstatic.net/hxh62.gif)

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)

**Tags:** computability, fractals
> **Comments:**
> **username_0**: After reading the FAQ I do not believe this belongs. It's probably not a reasearch-level theoretical computer science question. Sorry to post in the wrong place. Could someone recommend the proper forum to ask this question and/or move it there?  
> **username_1**: [math.se], [cs.se].  
> **username_0**: I considered posting on math.stackexchange since I participate there, but it seemed a little too algorithm-y. I didn't know that there is a computer science stack exchange. If the moderators want to move it to either of those places I wouldn't mind.  
> **username_2**: It's not obvious to me that this is off-topic here... obviously off-topic questions usually get more downvotes than upvotes  
> **username_3**: Can't you represent any fractal maze as a pushdown automaton, where the stack corresponds to the sequence of submazes that you're in? Then the solubility question would turn into the emptiness problem for context-free languages, which is decidable.  

---

## 2 answers

### Answer by username_4 on 2012-04-09. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: Wow! What a clever idea. I think this works but it's still a little fuzzy in my mind, so I'm going to take a bit of time to mull it over before accepting.  
> **username_0**: Ok yep pretty sure this algorithm is correct. Noting Peter Shor's comment above, I wonder if you could turn this around to provide a proof for the context-free language emptiness decidability problem..? For a given context free language emptiness problem, construct an equivalent fractal maze, then apply this algorithm.  
> **username_3**: @Nick: A fractal maze corresponds to a *reversible* pushdown automaton, where if you can make a transition from a state S to a state T, you can also make the transition from T to S. It should be straightforward to show that fractal mazes are in fact equivalent to reversible pushdown automata. There is a theorem saying that (up to polynomial factors) reversible Turing machines have the same power as regular Turing machines. I don't know if anybody has looked into reversible pushdown automata before, so I don't know whether anything is known about them.  
> **username_4**: @Peter: I found this [Reversible Pushdown Automata](http://www.springerlink.com/content/k653257805836718/), but the definition of "reversible" seems different. (P.S. congratulations for the simple and clean interpretation of a fractal maze as a PDA!!!)  
> **username_3**: @Marzio: nice reference. I suppose then that to avoid confusion, the things corresponding to fractal mazes should be called *symmetric* pushdown automata, in analogy with SL (Symmetric Logspace).  
> **username_0**: The above algorithm could be extended to directed graphs (irreversibe fractal mazes), you would just have $2n^2$ possible expansions to consider ($I_k \rightarrow I_j$ *and* $I_j \rightarrow I_k$).  

---

### Answer by username_0 on 2012-05-08. Score: 1

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](http://en.wikipedia.org/wiki/Hilbert_curve):

![Hilbert curve gif from wikipedia](https://i.sstatic.net/aYbwi.gif)

One could interpret this curve as a "fractal maze" with the following diagram:
![enter image description here](https://i.sstatic.net/N9IEe.png)

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:

![enter image description here](https://i.sstatic.net/tLcz4.png)

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.

> **Comments:**
> **username_4**: A naive comment: the "submazes" of the Hilbert curve are smaller, so in the "continuous world" it works; in the "discrete world" you'll never make an "exit" move because you continue to enter the first submaze (like an endless zoom on the bottom-left of the Hilbert curve). It resembles the [Zeno's paradoxes](http://en.wikipedia.org/wiki/Zeno%27s_paradoxes)  
> **username_4**: P.S. I think that there is no need of a fractal curve: a simple horizontal line from s to f with a single central submaze (which has a single horizontal line with a sub-submaze ecc. ecc.) leads to the same considerations.  
> **username_0**: Good point. If you do that with a sub-box of width 1/2 placed on the far right, it's not just like zeno's paradox, you get exactly zenos paradox. After further consideration it looks like the continuous definition isn't well suited for fractal mazes since it makes almost every fractal maze solvable.  
> **username_4**: but it is well suited for Zen labyrinth meditation (Google around for the difference between a labyrinth and maze in a meditation context) :-)  

---

