fractal mazeというのがあります。最初に提唱されたのはたぶんこのへん http://www.mathpuzzle.com/18Nov2003.html で、迷路全体のコピーが再帰的に迷路の中に埋め込まれている、こういうものです（画像は上記サイトより引用）。
これは別の見方をすると、下の図のように同じ部品がたくさん並んでいるということです。ちなみに下の図は説明のためにてきとうに描いたものなのでたぶんあんまり迷路としては機能してない
それで、いろいろと考えてたわけなんですが。
--------------------------------
1次元的な奴
とりあえず一番簡単な並べ方というとこういうのになる。mathpuzzle.comでも上述のfractal mazeの出現後こういうのが出てきたりしている（[http://www.mathpuzzle.com/17Dec06.html, Nov 13 2006]やら[http://www.mathpuzzle.com/23Dec2010.html, Aug 9 2010]やら）。というか下のやつみたいな左右に無限に伸びてるやつ、いつかのtopcoderで出てなかったっけ
--------------------------------
2次元的な奴
2次元のマス目状に並べるというのもできるな、と思った。
ところで、次のような話を先日知りました。
非負整数を保持しておけるレジスタ2つと、有限個の状態をとれるメモリがある機械がある。この機械を、与えられた初期状態から初めて、以下の規則を繰り返し適用して動かす。
・現在のメモリの状態がsでレジスタの値が(x, y)なら、メモリがs'、レジスタが(x+a, y+b)の状態に遷移する。ただしa,b∈{±1, 0}およびs'は、(s, 「xが0かどうか」, 「yが0かどうか」) の3つの情報だけから決まる。
このとき、与えられた初期状態から機械を動かして状態sに到達するかどうか、状態(s, (x, y))に到達するかどうか、などは決定不能である。
証明はこのへん https://www.jstor.org/stable/1970290 https://www.jstor.org/stable/2269811 にあって、まあ例によってチューリングマシンをシミュレート？エミュレート？します。xに素因数分解の指数の形でテープの情報とヘッドの情報をのっけて、yを使って簡単な掛け算や割り算などをxに施していってほげほげする。
これはつまりそうすると少なくとも、下のような「一方通行の道」を使って、「ほぼ周期的」な迷路（一本道だが・・・）を作ると、ゴールできるかどうかというのが決定不能になるということになります。マジ？なんかさすがに自信なくなってきたので有識者からのツッコミ等あればお待ちしております。
一方通行の道無しでどうなるかとか、「ほぼ」周期的というのがどのぐらい効いてくるかとかわからないですけど、こういうのを見ると同じ部品が2次元に周期的に並んだ迷路というのが決定不能でも全然おかしくないという気がしてくる。
ところで決定不能なのだとしたら、解の最小手数が問題の「見た目」に対して「考えられないほど」膨れ上がるような問題が存在する、ということで、パズル的にはオイシイわけです。誰かなんか面白いの作りませんかね。
ところでこんなやついつかのJOI関係のコンテストで出てなかったっけ、というのを思い出して調べたんですけどJOI open contest 2012 (JOI ninja contest) でした。そこではもちろん解ける問題として出題されていたのだと思うのですが、どこで違いが出てきたのだろう。やはり一方通行の道の存在が大きいのか、もしくは、壁の「端子」が1個しかない（→上の構成だと状態を持たせられない）のが大事？それとも両方向に無限に伸びてるというのが大事？
181230追記：これやっぱり節の最初に書いたような完全に同じ部品が並んでるような場合だと計算不能にならなそうな気がするというか、「端っこにきたときに特別な動きをする」というのが計算っぽいことをする（→停止問題に持ち込む）上で重要そうな気がする。
あと少なくとも到達可能性だけを問題にするんだったら端子1個ずつの場合なんてろくにパターンないやんけ、頭寝てた
190105追記：一方通行の道はなくても計算不能になりそうな気がする。generalized collatz（の初期値が指定されてるver）（というかFRACTRAN）あたりから素直に落としてこれる気がする、計算過程を逆走できてしまう問題があるかと思ったのだけど、計算終了の状態からそれ以上どこにもいけないようにしといたら問題なくない？
--------------------------------
fractal maze、別バージョン
フラクタルゲームというのを思い付いた。N×Nの方眼盤に1×1正方形の駒(小駒)または2×2正方形の駒(大駒)を二人交互に置いていく。各駒は縮小写像(盤を駒に縮小する写像)を表している。勝敗は「盤上の縮小写像の組で不変な自己相似集合」を連結にした方の負け。
— 盛田みずすまし (@nosiika) October 18, 2018
これ、一旦連結になったあと、連結じゃなくなったりすることもある。んー。ゲームになるか、ちょっと分からなくなってきました。
— 盛田みずすまし (@nosiika) October 20, 2018
これを読んで別の勝利条件を考えていて、たとえば「盤面の上と下が不変集合で分断されたら負け」というような勝利条件はいい感じに頭おかしそうでよさそうだな（あとfractal mazeみがあるな）と思ったんです。簡単のため縮小写像はN×Nを1×1に縮小するものだけにしましょう。
たとえば下の図で、下の辺から入って上の辺に抜けてみてください。左右は行き止まりです。表示がつぶれてしまっている箇所も微細な構造が無限に続いているものと思ってください。
ところで、これをプログラムで解こうと思ったときに行き詰ったのです。記事の最初で紹介したような端子と端子が結ばれている形のfractal mazeは、「『迷路全体の外側の端子がどうつながっているか』を保持しながら1段階ずつ図の深さを上げていく（接続状況が更新されなくなったらそれ以上深く探索しなくてよい）」という方法で解くことができるのですが（ここでそもそも勘違いしていたらごめんなさい）、上のような迷路でこれを行おうとすると、ナイーブには、深さを上げていくたびにどんどん接続関係を保持しないといけない開口部の個数が増えていってしまい、「状況が更新されなくなったらそれ以上探索しなくてよい」というような打ち切りが行えないのでは（→解が無い場合に延々と探索し続けることになる）という気がします。
どうすると解けるのでしょうか、はたまたさっきのみたいに決定不能だったりとかするんでしょうか、アルゴリズム強者氏からのお便りお待ちしております
