教室ブログ

2019.07.29

ビット

六十谷校

こんばんは。Wam六十谷校の川口です。
結城浩さんの新作が出ていたので読んでいました。
テーマはビットとバイナリーですが、全体を通して数学的に共通したものを提示することで、読者の数学への興味を誘う内容になっています。作中にも練習問題があったり、研究課題が載せられていたり、夏休みの自由課題としても楽しいです。まずは2進数の説明から入り、スキャナとプリンタのプログラムを例にフィルタを通すことで、1マス右に寄せる操作とdivで2で割って小数以下を切り捨てた実行結果が同じになることや、ビット反転がビット単位の排他的論理和になることを確認します。SWAPやREVERSEなどフィルタの操作がどの命令によって行われているのかを追っていきます。
それを応用したフリップ・トリップというゲームがあり、白いボタンが複数並んでいて、反転させると黒になります。これを全てのパターンを尽くすことでクリアになります。よくゲームの中のミニゲームで見たことがあるのですが多くの人は勘でパターンを見つけていくと思います。ボタン４つで始めて、ルールを探すために主人公もやはり勘で埋めていくのですが、その過程でハーフ・トリップ（3桁での組み合わせを尽くした状態）に辿りつくと、4桁目を除いた最上位ビットを反転させるとフルトリップができることに気付きます。これらの数列はm=log2(n&-n)になるのですが、y=ρ(n)+1としてグラフを書いたとき、定規のようになります。これがルーラー関数と呼ばれていることを初めて知りました。世の中には多くの不思議な関数があるので自分が知っているものは極僅かなのだと改めて思います。

フリップ・トリップとルーラー関数の繋がりが気になるところです。物理学者フランク・グレイに由来するグレイコードは1ビットを反転させることで次のビットパターンが得られるパターン列なのですが、作中フリップ・トリップ４はグレイコードの中でも標準的なもので、これを一般化して漸化式で表そうと試みます。ビットパターンでの定義なので表記も独特ですが、任意の正整数でグレイコードになっていることも証明してくれます。漸化式を見ることでビットパターンの個数と切り替わるビット位置で、ルーラ関数との共通点に気付くことができます。有名なハノイの塔問題もこれに応用できることも紹介されるのですが、このような中学受験で出るような、パターンを手を動かしながら考える問題が、美しい数列によって表現されていることに感動しました。

グレイコードは計算機科学の様々な分野で応用されていますが、2進数であり、有限列として日常的にあまり使わないのですが、無限列として表現したグレイコード展開は対称的な美しさであるフラクタル構造を持ちます。グレイコードの最初のビットを取り除く操作はテント関数と呼ばれるものになり、東大入試でも何度か出題されているf(x)=amin(x,1−x) で表されるテント写像になるようです。グラフが二等辺三角形を描くのでテント関数と呼ばれるようですが、 f(x) を n 個合成した関数 y=fのn乗(x) は初期値鋭敏性があり、これはカオス力学系の性質の１つです。
次にビットパターンを１が含まれている個数に応じて行に分けて表します。
1111
1110 1101 1011 0111
1100 1010 1001 0110 0101 0011
1000 0100 0010 0001
0000
各行ごとのビットパターンの個数に注目すると二項係数になっており、これを縦にまとめることでビットパターンを繋ぐ線を描くことができます。これで順序関係が入り、ハッセ図というものができます。これはポリトープ（n次元多面体）であり、アルゴリズムでは難しく人間の技量を必要とするようです。作中ではエピローグでいくつかのパターンが示されています。人の思考は限られた次元での幾何的処理を実行するのが精一杯だとどうしても考えがちなので、人間が介在する必要性が背反的で楽しいです。xからn個の辺を辿ってyまで行ける順序関係を論理和でx｜y=yと表せます。論理積でx=x&yとも表せます。順序関係の公理では反射律、反対称律、推移率があり、ビット演算では分配律も成り立ちます。分配律を満たす束と補元が存在する相補的束をブール束といいブール代数になります。最後に素因数分解での約数との関係もハッセ図で表せることを示してビットパターン、集合、約数をブール代数で見ることができると気付かせてくれます。

違う分野での対応する概念は数学だけに囚われず自然科学や文学にも見ることができます。わたしは歴史の関係性が見えないことが多いので、社会的にも対応する概念を他分野から繋げて記憶の助けとしたいと考えています。