この記事は、以前謎の一枚に出題した「図形パズル（https://nazo.pics/nazo/202001/00045）」という謎にまつわるしくじりの記録を文章化したくなったので書いたものです。当該問題の大幅なネタバレ（というかほぼ答え）を含むので、見たくない人は人は戻ってください。
----------------
「創作してえなあ～」という曖昧な感情は多くの人にあると思うんですよ。僕は２０２０年、これが「謎作りてぇなあ」という形で発露したので、年始頃にたまたま思いついたやつを謎の一枚に出題（https://nazo.pics/nazo/202001/00025）してみることにした。いわゆる初投稿である。
この謎は幸い何人かの方から好評をいただくことができた。
ちなみにこれは自分でも気に入ったので、そのあとリマスター版（注意：若干のネタバレ有：https://drive.google.com/open?id=1BCjcUf0ARxCHUSfIdHztoOnImiAJTkZi）も作った。僕はリマスター版の方が好みなんですけどどうでしょう。
↓ここからネタバレ
続きを読むfractal mazeというのがあります。最初に提唱されたのはたぶんこのへん http://www.mathpuzzle.com/18Nov2003.html で、迷路全体のコピーが再帰的に迷路の中に埋め込まれている、こういうものです（画像は上記サイトより引用）。
これは別の見方をすると、下の図のように同じ部品がたくさん並んでいるということです。ちなみに下の図は説明のためにてきとうに描いたものなのでたぶんあんまり迷路としては機能してない
それで、いろいろと考えてたわけなんですが。
--------------------------------
とりあえず一番簡単な並べ方というとこういうのになる。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つと、有限個の状態をとれるメモリがある機械がある。この機械を、与えられた初期状態から初めて、以下の規則を繰り返し適用して動かす。
・現在のメモリの状態が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）あたりから素直に落としてこれる気がする、計算過程を逆走できてしまう問題があるかと思ったのだけど、計算終了の状態からそれ以上どこにもいけないようにしといたら問題なくない？
--------------------------------
フラクタルゲームというのを思い付いた。N×Nの方眼盤に1×1正方形の駒(小駒)または2×2正方形の駒(大駒)を二人交互に置いていく。各駒は縮小写像(盤を駒に縮小する写像)を表している。勝敗は「盤上の縮小写像の組で不変な自己相似集合」を連結にした方の負け。
— 盛田みずすまし (@nosiika) October 18, 2018
これ、一旦連結になったあと、連結じゃなくなったりすることもある。んー。ゲームになるか、ちょっと分からなくなってきました。
— 盛田みずすまし (@nosiika) October 20, 2018
これを読んで別の勝利条件を考えていて、たとえば「盤面の上と下が不変集合で分断されたら負け」というような勝利条件はいい感じに頭おかしそうでよさそうだな（あとfractal mazeみがあるな）と思ったんです。簡単のため縮小写像はN×Nを1×1に縮小するものだけにしましょう。
たとえば下の図で、下の辺から入って上の辺に抜けてみてください。左右は行き止まりです。表示がつぶれてしまっている箇所も微細な構造が無限に続いているものと思ってください。
ところで、これをプログラムで解こうと思ったときに行き詰ったのです。記事の最初で紹介したような端子と端子が結ばれている形のfractal mazeは、「『迷路全体の外側の端子がどうつながっているか』を保持しながら1段階ずつ図の深さを上げていく（接続状況が更新されなくなったらそれ以上深く探索しなくてよい）」という方法で解くことができるのですが（ここでそもそも勘違いしていたらごめんなさい）、上のような迷路でこれを行おうとすると、ナイーブには、深さを上げていくたびにどんどん接続関係を保持しないといけない開口部の個数が増えていってしまい、「状況が更新されなくなったらそれ以上探索しなくてよい」というような打ち切りが行えないのでは（→解が無い場合に延々と探索し続けることになる）という気がします。
どうすると解けるのでしょうか、はたまたさっきのみたいに決定不能だったりとかするんでしょうか、アルゴリズム強者氏からのお便りお待ちしております
画像というのは2次元平面の各々の座標に色があるものなので、平面上の関数とみなすことができます。
以前からちょこちょこやっていたネタに、この平面を複素平面Cとみなして、C->Cの多項式や有理式やもっといろいろな有理型関数fを元の画像（関数）に合成して（引き戻して）新しい画像を作る、というのがあります*1*2*3*4。
最初やってたのはたぶんこのへんhttp://twilog.org/omeometo/date-130712
ところで、僕はボールジャグリングを趣味程度にたしなんでいます。過去にtwitterにジャグリングの様子をタイムラプスで撮影したらおもしろいんじゃないかと思ったりして動画（https://twitter.com/omeometo/status/731740192780902400）を上げたりしていました。
今回思ったのは、fの分岐点の周りを回るようにボールを投げて、その動画をfで引き戻したら、複数人でボールを渡し合っている感じになるのでは、ということです。
たとえばシャワー（Library of Juggling - Shower）を投げて、それを良い感じの写像で引き戻すと、下図のように、二人が横並びになってボールを投げ合ってる感じになる気がします。
実際に撮ってみたのが下です。上の図のような関数として(z-1/z)/2を考えます。逆関数の分岐点が±iにあるのでなんとなくそこをまたぐことを意識しながら投げます。体に分岐点がかぶるとグロニンゲンが生まれてしまうので結果的に割と高めに投げることになります。
www.youtube.com
まあまあそれっぽい感じに撮れ、満足
もっと極が多くてもいいんではということで、tan(z)でもやってみました。今度もz→i∞でtan(z)→iになるのでそこをまたぐように投げています
www.youtube.com
別に2人で横並びにならなくてもいいんじゃないかということで単純にz^2でもやってみました、別にこれでもいい気がします
www.youtube.com
*1:等角性より、小さい物体とか小さい部分の構造とかは基本的にそのままの形で残ることになります
*2:自分で思いついたものだったのですが、そのあと調べたら、conformal artやconformal photographyなどと呼ばれすでに名前がついている遊びでした。新しいことを思いつくのは難しい・・・
*3:こんな動画もありましたhttps://www.youtube.com/watch?v=CMMrEDIFPZY。人はなぜ顔を崩壊させて遊んでしまうのか
*4:オバマの動画、たぶん関数を切り替えるときには単純に古い関数と新しい関数の間を線形でつなぐみたいなことをしてると思うんですが、多項式の次数を上げたときにちゃんと無限遠からオバマが供給されてくるの、普通にめっちゃオモロイ
良い音が鳴りそうな数列をいくつか試しました
Thue–Morse sequence - Wikipedia, the free encyclopedia
https://dl.dropboxusercontent.com/u/66404075/thue-morse.wav
蝉
Rudin–Shapiro sequence - Wikipedia, the free encyclopedia
https://dl.dropboxusercontent.com/u/66404075/rudin-shapiro.wav
うるさい
この数列は自己相関が消えてるみたいなアレらしいのであんまり音程のある音にはならないのかと思ったらそうでもないんですね
Fibonacci word - Wikipedia, the free encyclopedia
https://dl.dropboxusercontent.com/u/66404075/fibonacci.wav
澄んだ音だ・・・心が洗われる・・・
というかこれに限らずsturmian word系はほとんど周期的だからなのかまともな音がする
Kolakoski sequence - Wikipedia, the free encyclopedia
https://dl.dropboxusercontent.com/u/66404075/kolakoski.wav
変なやつ、変な音
スペクトログラムも見てみたりするとどれも愉快なのでオススメです、RS seqとかスペクトログラムを見るとやっぱりまっ平らなのに音程があるので完全に謎
追記：なぜかchrome上で開いてなんかあの真っ黒な画面みたいなので聞くのと元ファイルで聞く（or ダウンロードして聞く）ので音が違うんだけどなんでだ・・・
特にfibonacci.wavとか全然違う音がしている、謎い
ぼく160406「辞書順でいろいろ鳴らして遊びました」
情報「Lyndon wordは辞書順でリストアップするのめっちゃ簡単にできるし長さがnの約数のやつを辞書順に全部つなげると辞書順で最小のde Bruijn sequenceが作れるよ」
ぼく「へえ」
https://dl.dropboxusercontent.com/u/66404075/lyndon.wav
音がケバい、注意
de Bruijn sequenceだからいろいろな音が鳴るかというとそういうわけではない
なんとなくボルテージが上がっていく感がある
というかなんかLyndon wordなんか組合せ論がいろいろあるし表現論でも出てきたりするらしい
いろいろと辞書式順序で鳴らして遊びました. 結構音がケバいので注意してください
長さを決めた0,1の列です. 2^n倍音が豊かに響きそうな雰囲気があるのでまあそういう音が鳴ります
https://dl.dropboxusercontent.com/u/66404075/lex_binseq.wav
順列です
https://dl.dropboxusercontent.com/u/66404075/lex_perms.wav
0,1の列で立ってる個数が決まってるやつです
https://dl.dropboxusercontent.com/u/66404075/lex_subset.wav
26日目の記事を書くだけの場所になってるのもアレなので変な音を鳴らした記録をてきとうにここに書いていこうと思います
pを素数とします. このとき, 整数aに対してpを法とした平方剰余記号 (Legendre記号) が定義されます. 超ざっくりいうとmod pでaが平方数なら1, 違ったら-1です (ただし
は0と定義します)
pを固定してaを0,1,...と動かすと数列になります.
たとえばp=3なら0,1,-1,0,1,-1,..., p=5なら0,1,-1,-1,1,0,1,-1,-1,1,...となります.
数列を見たら聞いてみよということわざがあります. 上の平方剰余記号の列をwavのサンプルの値だと思って聞いてみるとどのような音がするのでしょうか.
pが小さかったらただの周期的信号なので普通に音が鳴ります. 割愛します. pが大きい場合に興味があります. p~10^5だとだいたい2秒周期のwavができるはずです.
Quadratic residue - Wikipedia, the free encyclopediaとかの記述によれば, mod pでの平方剰余の分布はランダムな列と似ているそうなので, 大まかにはノイズが鳴るものと思われるのですが, 以下にp \in [100000,110000]からランダムに10個の素数を選んだものに対応するwavをあげておきます*1
https://dl.dropboxusercontent.com/u/66404075/heihou.zip
大まかにはノイズですが明らかに非ノイズな音もファイルによっては鳴っています. pによって様子が違いますが, ﾃｩｩｰﾝ↓ ﾃｩｩｩｩ↑ﾃｩｩｰﾝ↓ みたいな音が割と典型的です.
まあConclusionとかはなくて面白いなあという話なんですが, ﾃｩｩｰﾝの音が大きい素数と小さい素数の違いとか, 誰かわかりませんか
