コンピュータと数学の関係は、「大量の計算を速く行う」という一方向の話ではありません。数学は計算できる範囲、処理の手順、誤差の扱いを決め、コンピュータはその理論を実装して、シミュレーションや証明の検証に役立ちます。
ここでは計算可能性、機械学習、暗号、経路探索、数値シミュレーションを、手で追える小さな例で結びます。速い計算と正しい答え、予測と証明の違いを押さえると、AIや量子コンピュータのニュースも読みやすくなります。
数学が決める「計算できる」と「速く解ける」
チューリングマシンは計算の模型
チューリングマシンは、テープ上の記号を読み、内部状態と規則に従って書き換え、読み取り位置を動かす抽象的な装置です。実際のパソコンの部品配置を説明する図ではなく、アルゴリズムで何が可能かを考えるためのモデルです。
決定問題を扱う一つの定義では、次の七つ組で表します。
M = (Q, Σ, Γ, δ, q₀, qaccept, qreject)
| 記号 | 意味 | 単位 |
|---|---|---|
| M | チューリングマシン全体 | なし |
| Q | 内部状態の有限集合 | なし |
| Σ | 入力記号の有限集合。空白は含めない | なし |
| Γ | 空白を含むテープ記号の有限集合 | なし |
| δ | 現在の状態と記号から、次の状態・書く記号・移動を決める関数 | なし |
| q₀ | 初期状態 | なし |
| qaccept、qreject | 受理・拒否を表す別々の停止状態 | なし |
例えば「入力中に1があるか」を調べるなら、左から順に読み、1を見つけた時点で受理し、末尾までなければ拒否する規則を作れます。規則の数は有限でも、入力の長さを一つに固定する必要はありません。
対して停止問題は、任意のプログラムと入力について「いつか停止するか」を必ず正しく判定する万能なアルゴリズムを作れないという結果です。個々のプログラムの停止を証明できないという意味でも、すべてのバグ検査が無意味という意味でもありません。有限時間試して止まらなかったことと、永久に止まらないことの証明は違います。
計算量は秒数そのものではない
解ける問題でも、入力が増えると必要な処理が急増する場合があります。ビッグオー記法は、入力規模に対して処理量がどう増えるかを、大まかな上界として表します。
| 記号 | 意味 | 単位 |
|---|---|---|
| n | 入力要素の数など、明示した問題規模 | 個など |
| O(n) | 処理量が定数倍のnで上から抑えられる増え方 | 漸近的な増加の分類 |
| O(n²) | 処理量が定数倍のn²で上から抑えられる増え方 | 漸近的な増加の分類 |
一列のデータを一回ずつ見る処理と、すべての組を比較する処理を考えます。要素を100から1000に増やすと、前者の回数は約10倍、二重ループで全組を調べる後者は約100倍になります。CPUを少し速くするより、処理の組み立てを変える方が効く場合がある理由です。ただし定数やメモリ配置も実行時間に影響します。
線形代数で機械学習の一層を計算する
ニューラルネットワークでは、入力に重みを掛けて足し合わせる計算が繰り返されます。列ベクトルを使う約束なら、活性化関数を適用する前の値は次の式です。
Y = WX + B
| 記号 | 意味 | 単位 |
|---|---|---|
| X | 入力の列ベクトル | 例では標準化した無次元量 |
| W | 入力を出力へ写す重み行列 | 例では無次元 |
| B | 出力と同じ大きさのバイアスベクトル | 例では無次元 |
| Y | 線形変換とバイアス加算の結果 | 例では無次元 |
入力を(2, 3)、重みの一行目を(1, −1)、二行目を(2, 0)、バイアスを(1, −2)とします。一行目の出力は1×2−1×3＋1＝0、二行目は2×2＋0×3−2＝2なので、結果は(0, 2)です。行列の各行が、入力から一つの出力を作っています。
ここで入力は2成分、重みは2行2列、出力も2成分です。行列の掛け算を実装する前に形を確認すれば、向きの取り違えを防げます。実データに物理単位がある場合は、重みや出力の単位も整合させなければなりません。
この線形変換だけを何層重ねても、全体は一つのアフィン変換にまとめられます。複雑な非線形関係を扱うには活性化関数などが重要です。また「学習」は行列積を一回求めることではなく、損失関数に基づき重みを更新する過程です。行列演算、微分、統計がそれぞれ別の役割を担います。
暗号では整数の性質を安全性につなぐ
RSAの教材では二つの異なる素数を掛け、その積を公開します。ここでは仕組みを手で確かめるため、小さすぎて安全性のない数を使います。実用暗号の作成手順ではありません。
N = pq、φ(N) = (p−1)(q−1)
C = Me mod N、M = Cd mod N
| 記号 | 意味 | 単位 |
|---|---|---|
| p、q | 異なる素数 | なし |
| N | 法として使う積 | なし |
| φ(N) | Nと互いに素な1以上N以下の整数の数 | なし |
| e | 公開指数。φ(N)と互いに素に選ぶ | なし |
| d | edをφ(N)で割った余りが1となる秘密指数 | なし |
| M、C | 平文を表す整数と暗号文。0以上N未満 | なし |
| mod | 割った余りを取る演算 | なし |
例えばp＝3、q＝11ならN＝33、φ(N)＝20です。e＝3、d＝7とすると、3×7＝21の20による余りは1です。平文M＝4は、4³を33で割った余りの31に変わり、31⁷を33で割った余りを取ると4へ戻ります。
これは教科書的RSAの算術です。そのまま通信へ使うと、決定的な暗号化などに由来する問題があります。実用では十分な鍵長、乱数、用途に応じたパディング、実装の防御が必要で、NISTのRSA鍵確立に関する文書でもOAEP等を扱っています。ここで挙げた旧版は原理の参照であり、現行の適合性判断には最新版を確認する必要があります。
素因数分解できれば秘密鍵を得られることと、RSAを破るあらゆる方法が素因数分解と同値だという主張は別です。また、HTTPSの通信全体がRSAだけで暗号化されるわけではありません。暗号方式名だけで安全と判断せず、プロトコルや鍵管理まで確認することが大切です。
グラフ理論で最短経路を選ぶ
グラフは地点を頂点、移動可能な経路を辺として表します。辺に時間や距離を付ければ、近い順に見える道が本当に目的地まで短いかを計算できます。
例えばA→Bが2分、A→Cが5分、B→Cが1分、B→Dが4分、C→Dが1分とします。AからDへは、A→B→Dの6分より、A→B→C→Dの4分が短くなります。
ダイクストラ法は、未確定の地点のうち暫定距離が最小の地点を選び、隣接地点の距離を改善していきます。辺の重みが負でないことがこの方法の重要な前提です。負の辺を含む問題へ、そのまま適用してよいわけではありません。
ナビゲーションでは、距離、所要時間、通行料金のどれを小さくするかで答えが変わります。交通規制や時間帯による変化を入力しなければ、数学的には正しい最短経路でも現地では使えないことがあります。現実を何としてモデル化したかが、アルゴリズムと同じくらい重要です。
シミュレーションは方程式・条件・誤差をセットで読む
流体を計算する例
密度と粘度が一定の非圧縮ニュートン流体について、次の運動方程式と非圧縮条件を考えます。
ρ(∂u/∂t + (u·∇)u) = −∇p + μ∇²u + f
∇·u = 0
| 記号 | 意味 | 単位 |
|---|---|---|
| ρ | 流体の密度 | kg/m³ |
| u | 速度ベクトル | m/s |
| t | 時間 | s |
| p | 圧力 | Pa |
| μ | 粘性係数（動粘性係数ではない） | Pa·s |
| f | 単位体積当たりの外力 | N/m³ |
| ∇、∇·、∇² | 空間微分、発散、ラプラシアン | それぞれm⁻¹、m⁻¹、m⁻²の微分作用 |
元の式のμを動粘性係数と呼ぶと、単位が合いません。動粘性係数は粘性係数を密度で割った量で、単位はm²/sです。式の全項が単位体積当たりの力になっているかを調べれば、この違いを確認できます。
コンピュータでは空間を格子や要素に分け、時間も刻んで近似します。初期条件と壁面などの境界条件がなければ、方程式だけでは解は決まりません。格子を細かくしたときに結果がどう変わるか、保存則を満たすか、実験と合うかも確認します。数値が出たことは、一般の解の存在や滑らかさを証明したこととは違います。
SIRモデルで人口収支を確かめる
閉じた集団の単純な感染症模型として、次の人数表示を使います。実際の流行や個人の治療をこの模型だけで判断するものではありません。
dS/dt = −βSI/N
dI/dt = βSI/N − γI
dR/dt = γI、N = S+I+R
| 記号 | 意味 | 単位 |
|---|---|---|
| S | 感染し得る人の数 | 人 |
| I | 感染性を持つ人の数 | 人 |
| R | 回復などで感染過程から外れた人の数 | 人 |
| N | 一定と仮定した総人口 | 人 |
| β、γ | 感染の広がりと感染性の喪失を表す率 | 日⁻¹ |
| t | 時間 | 日 |
三つの変化率を足すと0になり、人口が保存されます。例えばN＝1000、S＝990、I＝10、R＝0、β＝0.3/日、γ＝0.1/日なら、感染への流入は2.97人/日、流出は1人/日、感染者の瞬間的な増加率は1.97人/日です。これは仮定値での計算例で、一日の実測人数を予言したものではありません。
混ざり方が一様、率が一定などの仮定を変えれば結果も変わります。同じβという記号でも、人数か人口比率かによって式と単位が変わるため、式の外見だけを他の記事から写してはいけません。
コンピュータの出力をどう確かめるか
一般的な二進浮動小数点では、0.1を有限桁で正確に表せません。Pythonで0.1＋0.2が表示上0.30000000000000004になるのは、その代表例です。Python公式の浮動小数点解説は、表現誤差と表示の丸めを区別しています。
一方、形式的証明では、定理と推論を厳密な言語で表して検査します。Leanの証明検証の説明にもあるように、形式化した命題が意図した内容か、使った公理は何かという確認も必要です。大量の具体例が成り立つことと、すべての場合の証明は同じではありません。
量子計算も数学的な条件を持つ技術です。重ね合わせにあるすべての答えを一度に読み出せるわけではなく、干渉と測定を利用する適切なアルゴリズムが必要です。AIによるコード生成でも同様に、出力を単位、境界値、独立した計算で確かめる作業は残ります。数学は計算を速くするだけでなく、どこまで答えを信じてよいかを判断する道具でもあります。
