Stardust Crown
論理などに関する小話を随時追加していきたいと思います。
Ａ：「次の私の質問に“はい”か“いいえ”で答えてください。ただし、嘘をついてはいけませんし、沈黙は許されません。」
Ｂ：「あなたの要求に応えてみましょう！」
Ａ：（ニヤリと笑って）「あなたは私のこの質問に“いいえ”と答えますね？」
Ｂ：（よく聞こえなかったと耳に手をやりながら）「はい？」
あなたは私のこの質問に“いいえ”と答えますね？
この質問に対して、“はい”か“いいえ”で答えなければなりません。実のところ、「嘘をつく」か「沈黙する」かを強いられることになりそうなのです。
というのは、「“いいえ”と答えますね？」と聞かれているので、もし「はい」と答えれば、“いいえ”と答えていないのに質問を肯定して嘘をついたことになるし、だからといって「いいえ」と答えれば、相手の尋ねた通り“いいえ”と答えたのに質問を否定してやはり嘘をついたことになるからです。
はい？
そこで「はい？」です。最後の「？」が重要ですが、これはイントネーション記号にすぎませんから、まず「“はい”か“いいえ”で答えてください」という要請は守っています。
次に、実はこの“はい？”は「何でしょうか？」という「よく聞き取れませんでした」という意味の「はい？」ですから、相手の質問を肯定したり否定したりする性質のものではありません。つまり、本質的に「嘘をつく」ということにはならないのです。
したがって、「“はい”か“いいで”で答え」、しかも「嘘をついてはいませんし、沈黙もしていない」と言えるわけです。
どうです？ 相手の要求に見事応えてみせたでしょう？
このお話は、平野敬さん @ QUIA の Wind Report 3/14（日）N 進法 における「１進法」に触発されて考えたものです。
ある数 A を、... a_2 a_1 a_0 [n] のような数の羅列で表す、一般的に用いられるｎ進法として知られている数の表記規則は、次の２つで成り立っていると言えるでしょう。
規則【い】は、一つの整数の表記法を有限の桁数において一意に定めるためにある規則のはずです。そして、これによってｎは２以上に制限されます。
しかし、この規則【い】を撤廃すれば、古典的なローマ数字などを「１進法」として説明できるようになります。
※この立場は「できるだけ多くの場合を包括的に説明できる規則が『優れた規則』だ」とするものです。
１進法では、規則【あ】に n=1 を代入した次の表記規則を用います。（記号の足し算で表現する考え方です。）
※自然数にのみ適用し、ゼロを用いないと決め、その他若干の規則を追加すれば一意性も保てます。
すると、例えばローマ数字なら、以下のような数字を用いた「１進法」だと理解できるわけです。（この他にも特殊な規則はありますが……。）
ところで漢数字についても、基本的には位の名前をどんどん設けていかなければなりませんから（例：十、百、千、万、億、兆……）、最初は「１進法」の仲間かと思ったのですが、表記に「足し算」だけでなく「掛け算」も利用していますね（例：四百＝４×１００）。十が基本単位になっていることもあり、近代的な十進法に近く、なかなか奥が深い感じがします。
※無理にｎ進法で説明しようとするなら、進行方向により大きい単位が連なっている限り、基数をそちらに揃えるといったちょっと複雑な規則が必要になりそうです。
よく、将棋や囲碁などを指して「こんな類のゲームは、いつかは三目並べのように結果のわかりきったものになってしまう」と言う人がいます。この主張の妥当性を、将棋を解き切るアルゴリムを実行することを想定し、考えてみましょう。
アルゴリズムの実行コストの物差しは主に２つあります。１つは時間複雑度（所要処理時間）、そしてもう１つは空間複雑度（所要記憶容量）です。
さて、将棋の最終的な結末の探索方法は、現在全探索しか知られていません。ところが、たとえ完全解を求めるアルゴリズムが記述できるとしても、その空間複雑度があまりにも大きいと、その完遂を物理的に保証できない場合があります。これは「（時間複雑度の問題から）完遂を待つのが実用的でない」という表現より根元的に困難であることを意味します。
将棋は完全情報確定的ゼロサムゲーム（参加プレイヤーには等しくすべての情報が事前に公開されていて、ランダムな要素がまったくなく、勝ち・引き分け・負けが確定する）であり、「互いに最善を尽くせば、あらかじめ先手必勝・引き分け・後手必勝のいずれかに決まっている（ただし恐らく後手必勝はない）」と考えられています。
しかしながら、将棋はオセロ等とは異なる性質があります。一つは、非収束のゲームであるということ、すなわち、ゲームがいくら進んでも一般に可能な手数は減少しないということです。（駒の数は減らないのですから。もちろん詰んだ場合は例外です。）そしてもう一つは、循環の可能性があり、同じ局面へループする場合があるということです。
したがって、「読み切る」検索を想定すると、縦型検索（深さ優先）は有効でなく、実質的に横型検索（幅優先）と同等の空間複雑度が要求されてしまうことになります。（なぜなら、手数の上限が不明であり、かつループを避けるために探索した局面のキャッシュが必要だからです。）
さて、横型検索を想定すれば、空間複雑度は将棋の全状態数になりうることになります。これはとてつもない数になりますが、一方でいくら大きくても確かに有限です。ですが、有限なら必ず読み切れるはずだと言えるのでしょうか？
実は、人間が取り扱いうる空間複雑度には明確な物理的上限があります。それは、全宇宙の素粒子数です。というのは、空間複雑度は所要記憶容量を意味するので、結果などを書き込む“スペース”が必要になるのです。しかしながら、どんなに節約したとしても、素粒子１個につき記憶容量１つが限界であると考えられます。
そして、（真剣に計算していませんし、厳密には判定困難ですが、）恐らく将棋の状態数は宇宙の素粒子数を超えるのではないでしょうか？ −そうなると、将棋は、どんなに技術が進歩したとしても、解き切ることは物理的にできなくなります。（メモリーが足りない！） ということで、人間は“将棋の最終的な結末”を知りうることができないかもしれないわけです。
「たとえ神様が将棋の結末を知っているとしても、人智においてそれを伺い知ることは不可能である。」という示唆を与えるお話でした。
※このアイデア自体は私のオリジナルではありません。
著作・制作／永施 誠