帝冠諸邦の計算屋

0d012: 万能計算機械 2

「最初の状態に相当するのは表の一番左上、なので書き換えずに機械を一つ左に動かす……」

ケレメンは表を見ながら呟いた。

: : 1 X X X _ _

* = * * = * * = * * = *

a a< a >b a a< a >c

: : 1 1 X X _ X

* = * * = * * = * * = *

b >b b >b b >b b a<

: : 1 1 X 1 _ :

* = * * = * * = * * = *

c >c c >c c >c c .

「次は？」

「1に当たったのでそれをXに書き換え、機械の状態をbにして右へ」

そうやって、ケレメンは機械に相当する磁石を行ったり来たりさせながら作業を進めていった。

手番0 初期状態

____:11111:__________ : :

* * = *

a a a<

手番1

____:11111:__________ 1 X

* * = *

a< a >b

手番2

____:1111X:__________ : :

* * = *

>b b >b

手番3

____:1111X:__________ _ X

* * = *

>b b a<

手番4

____:1111X:X_________ : :

* * = *

a< a a<

手番5

____:1111X:X_________ X X

* * = *

a< a a<

手番6

____:1111X:X_________ 1 X

* * = *

a< a >b

手番7

____:111XX:X_________ X X

* * = *

>b b >b

手番8

____:111XX:X_________ : :

* * = *

>b b >b

手番9

____:111XX:X_________ X X

* * = *

>b b >b

手番10

____:111XX:X_________ _ X

* * = *

>b b a<

手番11

____:111XX:XX________ _ X

* * = *

a< b a<

手番12

____:111XX:XX________ X X

* * = *

a< a a<

「この機械がやっていることがなんとなく掴めてきましたよ」

白墨を置いてケレメンは言う。

「説明してみたまえ」

「a状態は左へ左へと向かって、1にぶつかるまでそれを繰り返します。そして1を見つけたら、b状態へ変化する。そして右へ右へと進んでいて、紙帯(リュバン)の何も無いところまで進んだらXを置いてa状態へと変化する……」

「その通り」

そう言って、ノヴァーク博士は珈琲を口に運んだ。

「言うなればa状態は1を探していて、b状態は見つけた1を右に運んでいる。一度に運べるのは一つまでで、一度運んだ左側の1はXに置き換わっているから二度運ぶことはない」

「単純な手順でも、それなりに色々とできるだろう？」

「少し改良すれば、例えば入力として与えられた数を二倍か三倍といった固定倍するまでは行けそうです」

「具体的な手法は？」

「内部状態をもっと増やします。bのかわりにb²やb¹を作って、右の方にXを下ろすたびに数を減らしていけばいい」

ノヴァーク博士は小さく頷いた。

「……で、これって続きを書いたほうがいいですよね」

「最後の終止符(ポント)までしっかりと、だ」

ケレメンはノヴァーク博士の静かな微笑みを見て、あとどれだけの手番が必要なのかすぐに計算できない自分の知性を恨めしく思った。

手番13

____:111XX:XX________ X X

* * = *

a< a a<

手番14

____:111XX:XX________ X X

* * = *

a< a a<

•

•

•

手番44

____:1XXXX:XXXX______ X X

* * = *

a< a a<

手番45

____:1XXXX:XXXX______ 1 X

* * = *

a< a >b

手番46

____:XXXXX:XXXX______ X X

* * = *

>b b >b

•

•

•

手番54

____:XXXXX:XXXX______ X X

* * = *

>b b >b

手番55

____:XXXXX:XXXX______ _ X

* * = *

>b b a<

手番56

____:XXXXX:XXXXX_____ X X

* * = *

a< a a<

•

•

•

手番65

____:XXXXX:XXXXX_____ X X

* * = *

a< a a<

手番66

____:XXXXX:XXXXX_____ : :

* * = *

a< a a<

手番67

____:XXXXX:XXXXX_____ _ _

* * = *

a< a >c

最後の1を運び切る手順を終えたケレメンは、このままでは運ぶものがなくなって機械が止まらずにずっと左の方へと1を探し続けてしまうのではないかと心配した。とはいえ、きちんと手順を確認するとそのようなことが起きないように工夫がされていた。

「ここで状態cが出てくるんですか」

改めてケレメンは表の一番下の段を確認した。

: : 1 1 X 1 _ :

* = * * = * * = * * = *

c >c c >c c >c c .

「何をしようとしているか、見当がつくかい？」

「右に素通りして……いや違う、通り過ぎたところのXを1に書き換えていますね。そして何も書かれていないところにに到着したら区切りの記号を置いて終了、ですか」

四つの変化を確認して言ったケレメンに、ノヴァーク博士は首を縦に振った。

「遷移表の読み方がわかってきたようだね」

「これ、そういう名前だったのですか」

「別にそのままだがね」

手番68

____:XXXXX:XXXXX_____ : :

* * = *

>c c >c

手番69

____:XXXXX:XXXXX_____ X 1

* * = *

>c c >c

手番70

____:1XXXX:XXXXX_____ X 1

* * = *

>c c >c

手番71

____:11XXX:XXXXX_____ X 1

* * = *

>c c >c

•

•

•

手番79

____:11111:1111X_____ X 1

* * = *

>c c >c

手番80

____:11111:11111_____ _ :

* * = *

>c c .

手番81 停止

____:11111:11111:____

*

.

「……終わりました」

「実際に機械にやらせる時には、作業が終わった時に鐘でも鳴らしたほうがいいだろうな」

そう言うノヴァーク博士は作業の途中で少しずつ飲まれて空になっていたケレメンの珈琲を継ぎ足して言った。

「確かに、これは自動機械に任せたい作業ですね」

ケレメンは指を鳴らすように折り曲げて言った。

「最終的に81手番を要したわけだが、これは移動させる数が増えるとどうなると思う？」

ノヴァーク博士の質問に、ケレメンは椅子に座って考え出した。

「右に行ったり左に行ったりというのが、その回数だけではなくて移動距離も同時に増えますよね。たぶん増えていく数列を足していくことになるでしょうから……ええと昔やったなこういう問題」

「等差数列の和、というやつだ。式の導出の方法はいくつかあるが……そこまでわかっているなら答えを言ってしまおう」

そう言ってノヴァーク博士は立ち上がり、白墨を手に取った。

「 $2 x^2 + 5x + 6$ だ。$x$ は移動させたい数とする」

「単純な式になるんですね」

「この作業を、例えば1000という数字の移動に対して行うとどうなる？」

「……二百万と、五千と、六」

「五千と六については全体から見れば誤差のようなものだろうが、な。もちろん、これは数を一進記数法(エゲシュ・サームレンツェル)なんてものを使って表現したから起こった弊害でもある。本来なら十進法で四つ、二進法でも十の数を移動させるだけで良かった」

ケレメンは頷いた。深く頷いた。

「基本的に私は今まで理論分野しかやってこなかったから断言はできないが、おそらく問題を解けるようにする過程でできるだけ作業量を減らす工夫は求められるだろう。それも小手先のものではなく、手順そのものの発想を変える必要が出てくるかもしれない」

「……その手のものは、あまり得意ではありませんね」

「私も苦手じゃないが、できるかと言われれば難しい。もちろん、いくつかの例では単純な解法とは違ったより高速な手順が作り出せるがね」

「例えば、どのようなものでしょうか？」

「辞書」

ノヴァーク博士は既に考えていた案を口にした。

「辞書……ってあの、単語の意味が掲載されている？」

「それも文字順に、だ」

そう言って、ノヴァーク博士はケレメンの机の上に置かれていた統一都市同盟共通語-帝冠諸邦共通語の電気技術用語辞書を渡した。

「熱電子管(ヴァルヴォラ・テルモヨーニカ)という単語を探すとしたらどうする？数百枚の紙をめくりながら一つ一つの単語が探しているものと一致するかどうか確認していては日が暮れかねないが」

「開き癖……ではないですね。探す時、できるだけ視野を狭くしたほうがいいでしょうか？」

ノヴァーク博士の問う内容に察しのついたケレメンは聞いた。

「そうだ。理想的な辞書なら一頁に一単語しかなく、一度に開けるのは一頁のみと言ったところだろう」

「真ん中を開いて、文字順でその単語がそこより前にあるか後にあるかを見ます。そうすれば単語のある可能性がある範囲を絞ることができる」

「では、仮に $x$ 個の単語がある辞書ならどのくらいの手番が必要になる？」

「……ええと、何かありましたよねそういうもの。対数だ」

課題で出された計算のために古本屋で買った対数表を手に作業をしていたのをケレメンは思い出した。

「そう。概ね $\log_2 x$ 回の操作で求める単語が見つけられる。もちろん、それが辞書の中にあればだが」

「どんな大辞典に乗っている単語数だろうが、対数を取ってしまえばそこまで恐れるものではなくなる、と」

「その通り。逆に、もし手数が指数的に増える問題があったとすれば、それはおそらくどんな高速な機械であってもあまり大きな数を扱うことができなくなってしまうだろう」

そう言って、ノヴァーク博士は満足そうに珈琲を飲んだ。