計算機を作ろう　蛇足①

蛇足という名の言い訳です。

本編はこちらからどうぞ

○ 前書き

まさかの全体の前書きです。前とは一体･･････

当初の前書きをそのまま載せてみます。文末非統一なのが雑ですが、ご了承ください。

ーーーー（前書きここから）ーーーー

１　野下さんのリレー随筆
詰パラ９９年１月号のリレー随筆（pp.26-7）は、計算機科学者の野下浩平氏が執筆しています。タイトルは「看寿のコンピュータ」。

看寿の時代（１７００年代）に既に、「コンピュータの能力のもっとも基本的な『ループ』」の一例に到達していた

という内容のエッセイだが、その一部が、“ザ・計算機科学”という内容なので、参考にそのまま抜き出してみたい。

さて、詰将棋の表現力の豊かさはどこからくるのであろうか。将棋に現れる局面の数は有限である。盤の一マスに駒の置き方が三十通りほどあるとして、全体でその八十乗くらいとなり、ざっと十の百乗通りの局面があることになる。この数は膨大であり、調べつくそうとしても人間もコンピュータもかなわぬことは確かである。しかし単にそれだけで将棋が複雑であるとは納得できない。やはり、将棋の複雑さは、盤の上で豊富な表現のできる「計算機構」を実現できるかどうかによる、と考えてみたい。
　多少こみいってくるが、話をほんのちょっと正確にしよう。将棋や囲碁を一般化して、任意の大きさの盤の上のゲームとする。囲碁の方は自然に一般化できるが、将棋の方は歩をたくさん並べるというようにやや強引に一般化する。そのように一般化したゲームは、一種の計算機構、つまりコンピュータのモデル、と考えることができる。そしてこのゲームを用いて、十分複雑な計算の過程を真似（シミュレート）できる、ということが示されている。ここで、十分複雑な計算とは、現実のコンピュータを使って、例えば一時間、一日、一年とか（一世紀とか）の現実的な時間内でできるような計算をすべてふくむほどのものである。あらっぽくまとめると、ゲームによって、実際に考えられるような計算はなんでもできるということである。

１９９９年の論文に、「一般化詰め将棋問題の計算複雑さ－小駒図式、成駒無し、還元玉、都詰の考慮」というものがある。この論文では、ハミルトン閉路問題という問題を真似（シミュレート）している。（正確にはより細かく分類された次元制限付き有向ハミルトン問題を真似できる）

ちなみに、ハミルトン閉路問題は以下のような問題である。

f:id:tanpe_kanpinuyep_ne:20200102000647p:plain

☆から出発して、すべての頂点を１度ずつ通って☆へ戻ってくる経路が存在するか？

上の図には条件を満たすルートが存在するが、例えば下の図ではそのような経路は存在しない。したがって、ハミルトン閉路問題は、すべて解がある訳ではなく、解があったり無かったりすることに注意しなければならない。

f:id:tanpe_kanpinuyep_ne:20200102000940p:plain

　ここから以下のようにして、計算機構を実現できることが判明している。
①（拡大盤）詰将棋は、ハミルトン閉路問題をシミュレートできる。
＝どんなハミルトン閉路問題が与えられても、詰将棋の盤上でそのコピーを作ることができる。さらに、ハミルトン閉路問題の解の有無と詰将棋の詰不詰が一致する。

②ハミルトン閉路問題は、SATと呼ばれる論理学の問題をシミュレートできる。
＝どんなSATの問題が与えられても、それをコピーしたハミルトン閉路問題を作ることができる。以下同文。

③SATは、現実的な時間だけ作動する計算機（チューリングマシン）をシミュレートできる。
＝どんな現実的な時間だけ作動する計算機（withプログラム）が与えられても、それに対応するSAT問題を論理式として構成できる。計算機がちゃんと計算出来るか（バグらないか）とSAT問題の解の有無が一致する。

①から③をまとめると、現実的な時間内で計算可能な計算機に対して、SAT→ハミルトン閉路→詰将棋というルートでそれに対応する問題を構成することができる。つまり、詰将棋は十分複雑な計算の過程を真似することができる。（証明終わり）

野下さんのエッセイで言われていたことは、たぶんこのことだと思われる。
・・・もっと直接的に計算機を真似することはできないだろうか？

ーーーー（前書きここまで）ーーーー

前振りに時間を掛けても本編に辿り着けなければ意味が無いので、後回しにしました。当初の原稿は、この後にチューリングマシンの解説を行います。ここまで見ていただいた方は分かるでしょうが、この部分もばっさりカットしました。

さて、この前振りを行おうと思った理由は、実は一応存在します。

ひとつには、「拡大盤で計算模型を作る意義が書けるため」です。

自稿の内容は、9×9の詰将棋に応用できる部分をほとんど持っていないと思います。それでも、野下さんのエッセイを引用して、それっぽいことを述べるだけで、興味を持つに値するものだと言うことが可能となります。

が、逆に、もうひとつの理由は、

「わざわざチューリングマシンを組み立てる意義が薄いことを示すため」だったりします。野下さんがエッセイを書いた1999年のタイミングで、拡大盤の詰将棋に十分な計算能力があることがわかり始めていたのだと思います。

今回私はチューリングマシンを構成しました。しかし、それが殊更すごい成果だという訳ではなく、これまでの研究の自然な帰結（というか系）であるということは自白しなければならないでしょう。それをさらっと仄めかすことにも、この前書きは役割を持ってくれる予定でした。

1999年のタイミングで、拡大盤詰将棋の詰判定がNP困難であることが示されていました（上記論文）。これが、2000年～2001年にはEXPTIME完全であることが証明されます（その⑦で挙げた論文）。

また、

・NP ⊆ PSPACE ⊆ EXPTIMEであること

・倉庫番のPSPACE完全性の証明に線形拘束オートマトンの構成が使われたこと

を考慮すると、2000年～2001年の段階で、理論的には（「現実的な時間内で」という注釈を無くした）チューリングマシンを組み立てることができたのではないかと思っています。

･･･思っていますが、知識が無いのでよく分かりません（言い訳）。

※自稿で時間が掛かった部分の大半は、このあたりの分からない部分をどう誤魔化すかに割かれています。ここでは、諦めるという形で対応しました。

例えば、

One important case is Boolean logic--in which any finite computation can be encoded (for example with Nand gates), but which cannot support the unbounded computations considered for Turing machines (...)

Wolfram 2,3 Turing Machine Research Prize: Technical Details

と言われて、「NANDゲートじゃダメなのか」となった後で、