計算理論・ラムダ計算の問題

難易度 3大学院入試の専門科目の標準レベル証明問題大学院数学計算理論・ラムダ計算

$Σ = {0, 1}$ とし、 $Σ^{*}$ を空列 $ε$ を含む有限 2 進列全体、 $∣ x ∣$ を列 $x$ の長さ、 $Σ^{n}$ を長さ $n$ の列全体とする。万能チューリング機械 $U$ を 1 つ固定し、 $U$ が計算する部分関数 $U : Σ^{*} ⇀ Σ^{*}$ は、任意の $x \in Σ^{*}$ に対して $U (p) = x$ となる $p \in Σ^{*}$ が存在するものとする。 $x \in Σ^{*}$ のコルモゴロフ複雑性を
$C (x) = min {∣ p ∣ : p \in Σ^{*}, U (p) = x}$
で定める（ $U (p) = x$ は、入力 $p$ で $U$ が停止して $x$ を出力することを表す）。

任意の正の整数 $n$ に対して
$\frac{1}{2 ^{n}} x \in Σ^{n} \sum C (x) > n - 2$
が成り立つことを証明せよ。

この問題で使うもの

記述複雑性とカウンティング論法（説明と入口の問題）
等差・等比数列の和と Σ（説明と入口の問題）

この問題を解けるようになるまで（11 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「短いプログラムは少ない」ので「複雑性の小さい列も少ない」というカウンティング論法を使う。平均を直接計算するのではなく、 $C (x) \geq k$ となる列の個数で評価する。

ヒント 2

各 $x$ に最短プログラムを 1 つ対応させる写像は単射なので、 $C (x) \leq j$ となる $x$ は長さ $j$ 以下の列の個数 $2^{j + 1} - 1$ 個以下である。また、非負整数 $c$ は $c = \sum_{k \geq 1} [c \geq k]$ と書ける。

ヒント 3

$N_{k} = # {x \in Σ^{n} : C (x) \geq k}$ とおくと $\sum_{x \in Σ^{n}} C (x) \geq \sum_{k = 1}^{n} N_{k}$ であり、補題から $N_{k} \geq 2^{n} - 2^{k} + 1$ が得られる。あとはこれを $k = 1, \dots, n$ で足し合わせる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

各 $x$ に最短プログラムを対応させる写像が単射であることを、 $U$ が関数であることから示している（2 点）
長さ $j$ 以下の列が $2^{j + 1} - 1$ 個であることから、 $C (x) \leq j$ となる $x$ が $2^{j + 1} - 1$ 個以下であることを導いている（2 点）
$\sum_{x \in Σ^{n}} C (x)$ を $C (x) \geq k$ となる列の個数 $N_{k}$ の和で表し、 $k \leq n$ の範囲で下から評価している（2 点）
補題を $j = k - 1$ に使い、 $N_{k} \geq 2^{n} - 2^{k} + 1$ を得ている（2 点）
$k = 1, \dots, n$ で和をとって平均が $n - 2 + \frac{n + 2}{2 ^{n}}$ 以上になることを計算し、 $n - 2$ より大きいと結論している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針: 「複雑性が小さい列は少ない」ことをプログラムの個数で押さえ（補題）、平均を「 $C (x) \geq k$ となる列の個数」の和に書き直して評価する。

補題. 任意の整数 $j \geq 0$ に対して $# {x \in Σ^{*} : C (x) \leq j} \leq 2^{j + 1} - 1$ 。

証明. 仮定より各 $x \in Σ^{*}$ に対し $U (p) = x$ となる $p$ が存在するので $C (x)$ は有限な非負整数として定まる。各 $x$ について、 $U (p_{x}) = x$ かつ $∣ p_{x} ∣ = C (x)$ となる $p_{x}$ を 1 つ選ぶ。 $x \neq = y$ ならば $U (p_{x}) = x \neq = y = U (p_{y})$ であり、 $U$ は（部分）関数なので同じ入力に異なる値を返さないから $p_{x} \neq = p_{y}$ 。よって写像 $x \mapsto p_{x}$ は単射である。 $C (x) \leq j$ のとき $∣ p_{x} ∣ \leq j$ だから、この単射は ${x : C (x) \leq j}$ を長さ $j$ 以下の列全体へ移す。長さ $i$ の列は $2^{i}$ 個なので、長さ $j$ 以下の列は
$i = 0 \sum j 2^{i} = 2^{j + 1} - 1$
個。したがって $# {x : C (x) \leq j} \leq 2^{j + 1} - 1$ 。 $□$

本題. $n$ を正の整数とし、 $N_{k} = # {x \in Σ^{n} : C (x) \geq k}$ とおく。

(1) 和の書き換え. 非負整数 $c$ について $c = \sum_{k = 1}^{\infty} [c \geq k]$ （ $[\cdot]$ は条件が真なら $1$ 、偽なら $0$ ）が成り立つ（右辺は $k = 1, \dots, c$ の $c$ 個の $1$ の和）。これを $c = C (x)$ に用いて $x \in Σ^{n}$ について和をとると、有限和と非負項の和の順序交換により
$x \in Σ^{n} \sum C (x) = k = 1 \sum \infty N_{k} \geq k = 1 \sum n N_{k}$
（ $N_{k} \geq 0$ なので $k > n$ の項を捨てても値は増えない）。

(2) 各 $N_{k}$ の評価. $1 \leq k \leq n$ とする。 $C (x) \geq k$ でない $x$ は $C (x) \leq k - 1$ を満たすので、補題（ $j = k - 1$ ）より
$# {x \in Σ^{n} : C (x) \leq k - 1} \leq # {x \in Σ^{*} : C (x) \leq k - 1} \leq 2^{k} - 1.$
$# Σ^{n} = 2^{n}$ だから
$N_{k} \geq 2^{n} - (2^{k} - 1) = 2^{n} - 2^{k} + 1.$

(3) 合計. (1), (2) より
$x \in Σ^{n} \sum C (x) \geq k = 1 \sum n (2^{n} - 2^{k} + 1) = n 2^{n} - k = 1 \sum n 2^{k} + n = n 2^{n} - (2^{n + 1} - 2) + n .$
両辺を $2^{n}$ で割ると
$\frac{1}{2 ^{n}} x \in Σ^{n} \sum C (x) \geq n - 2 + \frac{n + 2}{2 ^{n}} .$
$n \geq 1$ より $\frac{n + 2}{2 ^{n}} > 0$ なので、右辺は $n - 2$ より大きい。

以上より、任意の正の整数 $n$ に対して $\frac{1}{2 ^{n}} \sum_{x \in Σ^{n}} C (x) > n - 2$ が成り立つ。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる