ピラミッド迷路

https://gyazo.com/3f905d9515486635dd99eae234e1a5cd

これ（を一般化したの）の決定不能性。

略証：

非負整数を保持するいくつかのレジスタと有限個の状態を持ち、各状態sについて次のいずれかの命令が（1つだけ）定められている機械（レジスタマシン？カウンタマシン？）を考える。

機械が状態sにあるなら、レジスタiをインクリメントして状態s'に遷移する。

機械が状態sにあるなら、レジスタiをデクリメントして状態s'に遷移する。ただしデクリメントによってレジスタの値が0未満になる場合は何もせず代わりに状態s''に遷移する。

レジスタが2個以上あれば、Turing完全になり、停止問題etc.は決定不能になることが知られている。

（略証：レジスタが潤沢にあれば普通にプログラムが組める。2個に減らすのは、一方のレジスタに2^a*3^b*5^c*7^d*...のような形で沢山の値を持たせ、もう片方のレジスタを用いて割り切れるかの判定や実際に割る処理などを行うことで可能。）

2個のレジスタの値(a,b)をピラミッドのブロックの座標（頂上から左下にa個、右下にb個移動した位置）に対応させ、各ブロックの中に状態の数だけ頂点を作り、プログラムの遷移に対応して辺を張る（画像：赤がインクリメント命令、青がデクリメント命令）ことで迷路ができるので、この形の迷路である場所からある場所に行けるかどうかの判定問題も決定不能になることがわかる。

https://gyazo.com/430cb41dca53e9345ad606450d0e6b3f

（実際は、迷路の道が一方通行でない場合「逆走」が可能だが、その場合も上の構成で決定不能性が示せる、はず。）

----------------------------------------------------

という文章を用意していたところ、twitter上の反応で「逆走」にどう取り合っていくかわからんというのがあったので一応僕の頭の中にある理屈をもう少し詳しく書いておきます。

まず上の略証の文章ではそもそも停止状態が用意されてないので停止状態を用意してちゃんと停止問題にしましょう。停止状態からは何も遷移しないものとしておく。（もうすこしうるさいことをいうならこのままだと各ブロックに1個ずつゴールがある形になってしまうので、停止状態に入ったらレジスタを全部クリアして真・停止状態に入るみたいなコードを追加してゴールを1つにしておく。）

停止状態には「逆走」して入ることはできない、というのと、「逆走」の直後に「順走」をするのは何もしないのと同じ（状態遷移が決定的なので）、というのを合わせて考えると、結局「順走」しかしない経路だけ考えればよい、となるはず。

----------------------------------------------------

追記：twitterで出した問題の答え。一番「浅い」解を示しています。

https://gyazo.com/fef6a92b62cf598456e9104b6214d8b3