計算機を作ろう　蛇足②

蛇足です。

前回の蛇足はこちら

詰将棋と並列計算

お題

よく見ると、今回構成したチューリングマシンは、適切に分岐させて、ルールを最善詰あたりにすれば、非決定性チューリングマシンになるように見えます。

（･･･という主張が真なら）詰将棋で作った計算機は、NP問題を多項式時間（≒多項式手数）で解くことが可能ということになります。

では、その威力はどのように示せばよいでしょうか。もちろん私は、NP完全問題を解くチューリングマシンを作った上で詰将棋に移植する能力は持ち合わせていません。

（※6分岐程度で弱音を吐くレベルです）

また、量子コンピュータとの違いもそんなに理解していません。上記Wikipediaでは「違うよ」と書いてあるので、違うのだと思います。

ところで、量子アルゴリズムを詰将棋に移植する方法は存在するでしょうか？

･･･道は険しい

今回の参考文献

※そういえば、昔作った禁欲協力詰バージョンも、「分岐ができる」＋「最短で詰ます」のだから、同様に並列計算が可能に見えてきました。どちらにせよ、プログラミング方法は分かりませんが･･････