帝冠諸邦の計算屋

0d015: 万能計算機械 5

「万能計算機械が確かに一通りの数学的問題を解けそうだ、ということはいい。ただ、これをもっと強化できないか、という疑問が出るのはもっともだ」

ノヴァーク博士の言葉に、ケレメンは座って頷いた。

「紙帯(リュバン)の本数を増やす。複数の機械を同時並行で動作させる。もちろんこういう機械は、もととなった計算機械以上に高速で、わかりやすい遷移表を持って表現できるだろう。ただ、それでもそれらが先程君が概略を作ったような万能計算機械によって再現できないわけではない」

「……具体的な方法はありますか？」

ケレメンの質問に、ノヴァーク博士は頷いた。

「例えば本数をいくら増やそうとも、それを一本にまとめることが可能だ。そうだな、紙帯(リュバン)を白と黒で交互に塗り分けるようなものだ。一本目の紙帯(リュバン)の文字は白の上に、二本めの紙帯(リュバン)の文字は黒の上に書けばいい。それぞれが干渉しないようにするためには補助的な機械の状態をそれなりに導入する必要があるだろうが、理論上は可能だ」

「……では、同時並行の方は？」

「これについては同じような方法でやればいい。白の機械と黒の機械を用意して、それぞれを交互に一手番ずつ進めていくわけだ」

「ええと、そうだ。紙帯(リュバン)ではなく黒板のように二次元ならどうでしょう。それなら一本の紙帯(リュバン)の上に置くのが難しくなります」

「可能だ。これについてはちょっとした技が必要だがな」

(-2, +2) (-1, +2)→( 0, +2)→(+1, +2)→(+2, +2)

↑ ↑ ↓

(-2, +1) (-1, +1) ( 0, +1)→(+1, +1) (+2, +1)

↑ ↑ ↑ ↓ ↓

(-2, 0) (-1, 0) ( 0, 0) (+1, 0) (+2, 0)

↑ ↑ ↓ ↓

(-2, -1) (-1, -1)←( 0, -1)←(+1, -1) (+2, -1)

↑ ↓

(-2, -2)←(-1, -2)←( 0, -2)←(+1, -2)←(+2, -2)

「紙帯(リュバン)が一次元の区切りを持つなら、二次元は格子になる。それは二つの整数の組で表すことができるわけだが、こうやって中心の原点から渦巻き状に数えていくことによって、それは一つの整数としても表すことができるのだよ。最初が1だとしたら、25に相当するのは一番左上、(-2, +2)にあたる。こうすれば、二次元に書かれた記号を一本の紙帯(リュバン)で置けるだろう？」

ケレメンは中心から矢印を追いかけるように目で辿った。まずは上。そして右。すぐさま下。そして左へ。既に通った場所を二度通ることはなく、そしてどの場所の点であってもいつかは必ず通過することになる渦巻きだ。

「……そうなるのはわかりました。では、どうやって機械でそれを実現します？右と左にしか行けないはずなのに、追加で上と下の分も対応できるのですか？それに、いくつかの点は二次元の上では隣り合っていても紙帯(リュバン)の上では離れていることがあるでしょうし」

「そこは万能計算機械と同じ手口になる。ある種の住所を記号の前に置いて、それを探すようにすればいい。次の住所を探すための方法を機械に実装することはそう困難じゃない」

「……こういう証明を、ずっとしていくのですか？」

「今も継続中だ。ただ、そろそろある種の合意が得られそうな程度には、私の万能計算機械を超えるま(・)と(・)も(・)な(・)方法は見つかっていない」

「……まともでない方法なら、あるかのような口ぶりですね」

「いくつかあるとも。私が作ったものでは予言者(ラートノク)と呼んだがね」

「何を予知するのですか？」

「その機械が停止するかどうか」

ノヴァーク博士の言葉に、ケレメンは少し黙って考えた。今まで作ってきた機械は相当複雑で、もし構築を少しでも誤れば、あるいは最初の紙帯(リュバン)の状態を適切に用意しなければ、その機械は永遠に動き続ける。

あるいは、永遠に動き続けることを目的とした機械もできるだろう。例えば無限に1を繰り返すような。もう少し実用的なものなら、素数を順番に書いていったり、あるいは円周率を終わることなく計算していくものもできるのだろうとケレメンは考えた。

具体的な方法には見当すらつかなかったが、おそらくノヴァーク博士に言えば自分の知らない定理を一つか二つどこからともなく持ち出してそのような機械を作れるだろう、と察しはつく。少なくとも、なにか便利な方法があるとは昔どこかで聞いた気はしていた。

「確かにわかりにくそうではありますが、つまりそれは……」

ケレメンはノヴァーク博士が以前に言った言葉を思い出していた。万能計算機械はあらゆる問題を解くことのできる機械ではない。それは他の紙帯(リュバン)式機械を模倣することで紙帯(リュバン)式機械に解ける問題を解けるが、もし原理上、紙帯(リュバン)式機械に解けない問題があれば？

口を開きそうになったノヴァーク博士は、息を吐いて考えるケレメンを見た。

「紙帯(リュバン)式機械が停止するかどうかは、紙帯(リュバン)式機械では解けない問題なのですか？」

「その通り。厳密に言えば、どんな紙帯(リュバン)式機械を与えられても、それが有限の時間で停止するか、あるいは無限に動き続けるかを判定できるような紙帯(リュバン)式機械はない」

紙帯(リュバン)式機械に紙帯(リュバン)式機械を読み込ませるにはどうすれば、と一瞬ケレメンは考えたが、それは先程作り出した万能計算機械と同じようにすればいいのだろうと察することができた。

「……証明は、できますか？」

「二通りの方法で。おそらく君に向いている方と、私の指導教官が使ったのと似た方法だ」

「どちらが難しいですか？」

ケレメンの言葉に、少しノヴァーク博士は唸った。

「前者は具体的に証明しろ、となると難しいな。専用の機械をきちんと設計する必要がある。後者はちょっとした集合論と量度(サーモシャーグ)と呼ばれる概念が必要だ。とはいえ、大まかな解説だけなら可能だろう」

「まずは、前者をお願いできますか？多少抽象的でも構いません」

「わかった。ではまず、予言者(ラートノク)機械を作れたとしよう。入力に使うのは遷移表と初期状態の紙帯(リュバン)を並べたもの。出力は停止するなら1、動き続けるなら0を出力するとする」

「……はい」

先に作ってしまうのか、とケレメンはなんとなく論点先取りの気配と、どこかで似たような方法を知っているかのような既視感を覚えていた。

「では、性格の悪い予言者(ラートノク)機械も作れる。もし与えられた紙帯(リュバン)式機械が停止するなら無限に機械が右に動きながら1を吐き出し続けるし、止まらないなら0の出力を1に変えて停止しよう」

ケレメンはこれを聞いて、自分の未来を知って逆らおうとする予言者を想像した。物語では、たいていこういう試みは介入によって失敗するのであるが。

「……性格が悪いですね、とはいえ、作るのはそう難しくなさそうです」

停止状態の先に新しい状態を作ればいい。一瞬だけの眠りから覚めた機械は、今までのことをすべて忘れて目の前の数字だけを見る。そしてもしそれが1であれば、もしかしたら膨大な計算の途中経過が残っているかもしれない右側の文字列を全て1で上書きしながら進んでいくのだ。

「ところで、この性格の悪い予言者(ラートノク)機械は、万能計算機械やもとの予言者(ラートノク)機械で処理できるような、遷移表と初期状態の紙帯(リュバン)を並べた入力を持つのはいいかね？」

念を入れるように言ったノヴァーク博士に、ケレメンは頷き、ノヴァーク博士が何をしようとしているのかに気がついた。

「性格の悪い予言者(ラートノク)機械を、性格の悪い予言者(ラートノク)機械に読み込ませる？」

「そうだ」

ノヴァーク博士は最高の悪戯を思いついたような笑顔を浮かべた。

「そうすると、奇妙なことが起こる。この機械は止まるだろうか？それとも、止まらないだろうか？」

「止まるとしたら、性格の悪い予言者(ラートノク)機械は動き続けるはずだし、しかしそうすれば性格の悪い予言者(ラートノク)機械は止まらなければならない……」

機械は完全に決定的で、邪魔の入る余地はない。そのようなことをすれば矛盾が起こるのであれば、それは最初の前提──予言者(ラートノク)機械の存在を仮定したところに誤りがある。

「実際にはもう少し論理的に説明するのだがね。君にはこのぐらいがわかりやすくていいだろう」

ケレメンはふと、自分が持っていた既視感に気がついた。中等学校でやった2の平方根が二つの数の比で表せないことの証明──背理法によって、予言者(ラートノク)機械が紙帯(リュバン)式機械で作れないことがさらりと証明されていたのだ。