algorithm termination
Source Link
Marzio De Biasi
  • 22.2k
  • 2
  • 52
  • 122

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 expansionexpansions).

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.

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 expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$.

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.

distinct internal/external edges for nested copies
Source Link
Marzio De Biasi
  • 22.2k
  • 2
  • 52
  • 122

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

  • suppose tahtthat 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"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 expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$.

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

  • suppose taht 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;
  • 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 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 expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$.

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 expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$.

Source Link
Marzio De Biasi
  • 22.2k
  • 2
  • 52
  • 122

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

  • suppose taht 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;
  • 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 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 expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$.