計算による実数の分類
新井 敏康（神戸大学工学研究科）

11/1/2007
ここでは断らない限り、数は自然数を、集合は自然数の集合を、関数は自然数上の部分関数、つまり定義域が Nn の部分集合である関数を意味する。

1

計算可能性
ここでいう 計算 は、紙に書けるような有限的な対象を入力として、ある固定された有限個の規則（アルゴリズム とか プログラム と呼ぶ）に則って、入力に対して機械的な操作を有限回施して出力を得るような過程である。
次のことを仮定する：

1. 出力は各入力に対して高々ひとつ。
2. 入力の引数はアルゴリズムごとに決まっている。
3. 計算の過程は離散的でひとつずつの計算ステップに分かれる。
4. 計算の各ステップは、入力を決めれば一意に機械的に定まっている。
（決定性）
5. とくに計算を始める状態と終わる、停止する状態は予めアルゴリムによって定められている。
上で述べた「計算」の概念はまだあまりにも獏としており数学的な定義ではない。しかしこれに見合う 計算可能性(computability) の正確な定義はいくつも提出され、しかもそれらはすべて同値であることが知られている。
先ず、入出力と計算の途中経過を記録する対象はすべて紙に書けるような有限的対象としたが、これらは本質的にいくつかの文字・記号から成る有限列と考えてよいだろう。するとそのような対象は自然数で表現できる。これを コード化（符号化 (en)coding）という。

1.1

コード化

コード化の例を見る。初めに長さに制限のない自然数の有限列 (x0 , . . . , xn−1 ) (n ≥0) をひとつの自然数 hx0 , . . . , xn−1 i でコードする。
1例えば pn を n 番目の素数 (p0 = 2, p1 = 3, . . .) として

hx0 , . . . , xn−1 i :=

Y

1+x

i
0
p1+x
= p1+x· · · pn−1n−1
0
i

i<n

と定めればよい。特に空列（n = 0）のコードは h i = 1 である。このときexp(x, i) = max{y ≤ x : pyi |x}（x を割り切る pi の最大ベキ）1 とすると(
n−1 n>0n−̇1 :=
0n=0
について、復号化(decoding) (x)i と列（のコード）x の 長さ(length) lh(hx0 , . . . , xn−1 i) =

nは
(x)i

= exp(x, i)−̇1

lh(x)

=

min{i ≤ x : exp(x, i) = 0}で与えられ、また列のコードの集合 Seq はx ∈ Seq ⇔ ∀i ≤ x(pi |x → i < lh(x))
また

x 6= 0 → (x)i < x ∧ lh(x) < x(1)ともなっている。
一般に記号 a0 , · · · , aN から成る文字列 x0 · · · xk をコード化するには、先ず、各記号のコード dai e を定め、（例えば、ai のコードを dai e = pi ）文字
列 x0 · · · xk のコードを hdx0 e, . . . , dxk ei とすればよい。
これで計算に関わるプログラム、入出力、計算過程はすべて自然数でコードできるので自然数であると思ってよいことになる。
以下で全域的でない関数（部分関数(partial function)）を扱うので、少し記法を定めておく。
値を持たない、定義されていない(undefined) かもしれない式 e, f について、e ↓ は e が定義されていることを表し、e ' f は、両辺が定義されていてそれらの値が等しいか、もしくは両辺ともに定義されていないことを表す。
自然数上の関係 R(n) について、µn.R(n) で、R(n) を満たす自然数が存在すればそのような最小のものを表し、そうでなければ µn.R(n) は定義されない。
関係 R ⊆ Nk が 計算可能 とは、その特徴関数(
1 if R(~x)χR (~x) =0 otherwiseが計算可能なときにいう。
1 exp(0, i) = 0 と定めておく。

2

1.2

基本的な諸結果

上記の計算に対する理解のもとに次のことは正しいとしてよいだろう（「計算」の定義を正確に与えてないのだからいまのところ証明はできないが）。

1. 関係「列 y = hy0 , . . . , yk i は、引数 n のプログラム e に入力 ~x =(x0 , . . . , xn−1 ) を与えた環境での（k ステップまでの）計算過程（のコード）である」は計算可能である。これをComp(e, ~x, y)と書く。
ここで各 yi は計算過程中の計算状態を表し、yi+1 はその次の計算状態である。

2. 各 n についてTn (e, ~x, y)
で、「引数 n のプログラム e について Comp(e, ~x, y) かつ y = hy0 , . . . , yk iの最後 yk の計算状態は計算の終了状態である」を表すとする。これも計算可能である。
計算過程は一意的なので、Tn (e, ~x, y) を満たす y は e, ~x ごとに高々ひとつである。この y （が存在すればそれ）を e, ~x の 計算数(computation

number) と呼ぶ。
3. 計算数 y について計算結果（出力）を U (y) で表す。これも計算可能である。
4.
{e}(~x) ' U (µy.Tn (e, ~x, y))と定義する。
計算可能な（＝プログラムがある）n-変数部分関数 f について、e（そのプログラムのコード！）が存在してf (x0 , . . . , xn−1 ) ' {e}(x0 , . . . , xn−1 ) ' U (µy.Tn (e, x0 , . . . , xn−1 , y))となる (normal form thm)。

5. 計算数 s 以下の計算のみ考えて{e}s (~x) ' U (µy[y ≤ s & Tn (e, ~x, y)])とおく。すると明らかに{e}(~x) ' z ⇔ ∃s[{e}s (~x) ' z].
3

2

半計算可能集合集合 A が計算可能であるとは、n ∈?A という問いに Yes/No で（正しく）答えてくれるアルゴリズムがあるということである。これに対して、問い n ∈?A が正しい場合、そしてその場合に限って Yes と答え、n 6∈ A の場合には如何なる答えも出さない（計算が終了しない、定義されない）ようなアルゴリズムが存在するとき A は、半計算可能(semicomputable) と呼ばれる。
つまり、計算可能関数 {e} の定義域をWe := {~x : {e}(~x) ↓}と書き、計算可能関数の定義域になっている関係 R(~x)∃e∀~x[R(~x) ↔ ~x ∈ We ]が半計算可能ということになる。
補題 2.1 関係 R(~x) が半計算可能であるのは、ある計算可能関係 S により∀~x[R(~x) ↔ ∃y S(~x, y)]と表せるときである。
補題 2.2 K := {x : x ∈ Wx } = {x : {x}(x) ↓} は半計算可能だがその補集合は半計算可能でない。特に K は計算可能ではない。
しかもつぎの意味で、半計算可能集合の中で 完全(RE-complete) である：
各半計算可能集合 X について、計算可能関数 F でx ∈ X ⇔ F (x) ∈ Kとなるものが取れる。
証明. K が半計算可能なのは x ∈ K ↔ ∃y T1 (x, x, y) なので補題 2.1 よりよい。

K の補集合が半計算可能としてその指標 e を取る：
∀x[x 6∈ K ↔ x ∈ We ]ここで x = e と取ると

e 6∈ We ↔ e 6∈ K ↔ e ∈ Weとなり矛盾。よって K は計算可能ではない。

4

2

3

相対化
集合 A を 神託(oracle) として用いる計算（A-計算 もしくは A に相対化 された計算）の概念を導入する。これはプログラムの命令リストの中にn ∈?Aという新しい種類のものを加えることにより得られる。
つまり、A-計算の途中で得られた値 n について、n ∈ A かどうか訊いてその答え (Yes/No) を得てそれを後の計算に利用できる。
このような命令を含んだプログラムを A-プログラムと呼ぶ。A-計算で計算できる（部分）関数を A-計算可能関数という。
「A-プログラム e に入力 ~x を与えて計算を実行して計算が終了するまでの A-計算過程が y である」を表す TnA (e, ~x, y) は、A-計算可能で{e}A (~x) ' U (µy.TnA (e, ~x, y)).
ところで、終了する各計算過程は有限ステップで終了するので、その間に神託に伺いをたてるのも有限回である：計算数 y について、この計算では神託 A の内で高々 0 ∈?A, . . . , y − 1 ∈?A という問いしか発生していない。つ
まりこの計算はA|y := {i < y : i ∈ A}にしか依存しない。
いま集合 A の y までの情報を記録した数をXĀ(y) :=
2i ai
i<y

ここで

(
ai :=

1 i∈A
0 i∈
6 A

として Ā(y) を A|y と同一視する。上で述べたことは A-計算では有限情報

Ā(y) で足りているということである。
従ってある（相対化されない）計算可能述語 Tn,1 が存在してTnA (e, ~x, y) ↔ Tn,1 (e, ~x, y, Ā(y))となる。
相対化されていない場合と同様に計算数を限定して{e}Ax) ' U (µy[y ≤ s & TnA (e, ~x, y)]) ' U (µy[y ≤ s & Tn,1 (e, ~x, y, Ā(y))])
s (~
とおく。
すると明らかに{e}A (~x) ' y ⇒ ∃s[{e}Ā(s)(~x) ' y &smax{e, ~x, y} < s & ∀B∀t > s(B̄(s) = Ā(s) ⇒ {e}Bx) ' y)]
t (~
5

(2)

4

計算により比較不可能な実数の構成
集合 A, B について、A をその特徴関数 χA と同一視して、χA が B-計算

可能なとき、A は B に Turing 還元可能(Turing reducible) といって

A ≤T Bと書く。これは次と同値である：∀x[(x ∈ A → {e}B (x) ' 1) ∧ (x 6∈ A → {e}B (x) ' 0)]

(3)

また

A <T B :⇔ A ≤T B & B 6≤T A
同値関係

A ≡T B :⇔ A ≤T B ≤T A
で定め、この同値関係による同値類を 次数(degree) と呼ぶ。次数上にも関係≤T 及び <T は自然に拡張され、次数上では ≤T は半順序になる。
次数の理論は、D = P (N)/ ≡T 上での半順序 ≤T の構造を調べることを目的としている。集合 A の次数、すなわち A の属する ≡T に関する同値類
を [A] と書こう。
0 で計算可能集合の次数を表し、K の次数を 00 (jump) と書く。補題 2.2
よりどんな半計算可能集合 A についても

0 ≤T [A] ≤T 00 .
E. Post(1944) は、それまでに得られていた半計算可能集合が計算可能かも
しくは RE-完全な K と T -同値なものしかなかった、つまりそれらの次数でいえば 0 か 00 しかなかった状況から次の問題をたてた：

Post の問題：計算可能でないが半計算可能な集合 A で

A <T K となるものは存在するか？
これに答えたのが R. M. Frieberg(1957) と A. A. Muchnik(1956)（独立になされた）で、その手法は 優先論法(priority argument) と呼ばれ、後に様々に洗練されて次数の理論の主要武器としてその理論を深めた。

Frieberg と Muchnik は単に Post の問題に答えるだけでなく半順序 ≤T が線形順序でないことまで示している。
定理 4.1 (Friedberg-Muchnik の定理）
半計算可能集合 A, B で半順序 ≤T に関して比較不能なものがつくれる。
従ってその次数は 0 <T [A], [B] <T 00 である。

6

半計算可能集合 A と B でどんな e についても次の条件 R2e と R2e+1 を同時に満たすものをつくりたい：R2e: A 6= {e}BR2e+1

: B 6= {e}A

これは (3) によれば各 e ごとに数 x2e をつくり（x2e+1 も同様）

[x2e ∈ A & {e}B (x2e ) 6' 1] ∨ [x2e 6∈ A & {e}B (x2e ) 6' 0](4)としなければならない。
さて証明のアイデアであるが、先ず集合 A, B の構成および B-計算 {e}B (n)と A-計算 {e}A (n) をすべて時系列に並べて考える。時刻 s は計算のステッ
プ数にほぼ対応しているが、むしろ小節 1.2 で述べた計算数 ({e}B (n) 'U (µs.T1,1 (e, n, s, B̄(s)))) と思えばよい。集合 A, B の時刻 s までの部分情報を含む集合をそれぞれ As , Bs と書くとこれらは
1. As , Bs は有限集合。
2. {As }s , {Bs }s はともに増加列 (s < t ⇒ As ⊆ At ) で A =Ss Bs .

S

s As , B =条件 R2e つまり (4) を満たすことを考える。
もし {e}B (x2e ) 6' 0 なら x2e 6∈ A でよい。

{e}B (x2e ) ' 0 であるとしよう。このとき (2) より、十分大きい s についてs{e}Bs (x2e ) ' 0(5)となるはずである。そこで (5) のとき x2e ∈ As+1 (⊆ A) と定める。これによsり (4) を満たすためには、{e}Bs (x2e ) の計算が安定であればよい。つまり時t
刻 s 以降の t でもずっと {e}Bt (x2e ) ' 0 であればよいが、それには

B|s = Bs |s(6)となっていれば十分である。言い換えると、一旦時刻 s で (5) であるがゆえに x2e ∈ As+1 としたら、将来において B に s より小さい数を入れたくない。
tところが A と B の役割は対称なので、時刻 t > s で {f }At (x2f +1 ) ' 0となったら2 、x2f +1 ∈ Bt+1 としたくなる。(6) を充たすためには x2f +1 ≥ sとなっていてほしい。ところが計算が進行する前から予め x2f +1 ≥ s を充たすように大きく取っておくことはできない。そこで x2e と x2e+1 自体も時刻の進行とともに変動させていく。つまり（計算可能な）数列 {xse }s をつくり

xe = lim xses→∞

2 時刻 t でこうなるのは、計算が進んで {f }At (x2f +1 ) の計算が終了したか、あるいは At
tにその計算に必要な情報が t までに盛られたかである

7と定める。これは∃s[∀t ≥ s(xte = xse ) & xe = xse ]ということである。
状況を分かりやすくするため、異なる条件を満たす証拠は異なるようにしておく (e 6= f ⇒ xse 6= xtf )：つまり

xse ∈ {hy, ei : y ∈ N}と定める。
後で定義する数列 {xse }s は非減少列 s < t ⇒ xse ≤ xte となっていて、(xse )0 ≤ s(7)

つまり xse = hy, ei ⇒ y ≤ s となっている。
すると上で述べた状況は、時刻 s で (5) であるがゆえに xs2e ∈ As+1 として同時にこれ以降、つまり t > s で xt2f +1 > (xt2f +1 )0 ≥ s となるように{xt2f +1 }t を定義する。
しかしこれだけでは数列 {xse }s は上で述べた意味での極限を持たないかもttしれない。それはある t > s で xt2f +1 ≥ s が {f }At (x2f +1 ) ' 0 となり、この計算を安定にするために u > t で (xu2e )0 ≥ t > s ≥ (xs2e )0 としてしまうと、数列 {xs2e }s が発散してしまう怖れがあるからである。
そこで、条件 Re において、より小さい添字（＝プログラム）e に高い
優先度(priority) をつける。そして R2e について時刻 s で (5) となったら
xs2e ∈ As+1 とすることで時刻 s + 1 では R2e が充たされるようにするが、（R2e+1 も同様）、より高い優先度の Rf (f < 2e) がそれを 覆す(injure) つま
り例えば t > s でtt
2f + 1 < 2e & {f }At (x2f +1 ) ' 0となったら xt2f +1 < s であって (6) を壊すのだが、xt2f +1 ∈ Bt+1 として、この時点での条件 R2e は優先度の高い R2f +1 により覆されてしまい、xt+12e ≥ tと新たに設定し直される。しかしこの「賽の河原積み」は各 e について有限回しかなされず、極限 xe = lims→∞ xse が存在することが分かる（補題 4.2
参照）。
以上で証明の概略が説明し終わったので、正式な構成をしよう。以下で、有限集合 As , Bs と数 xse , res を同時に s に関する帰納法で定義する。s 7→(As , Bs , xse , res ) は計算可能となる。
res は res = 0, 1 で、res = 1 ということは「条件 Re を充たすための変更が
時刻 s かそれ以前になされ、かつ s に至るも尚その変更が覆されていない」ということを示すことになる。
初めに
A0 = B0 = ∅, x0e = h0, ei, re0 = 0.
8

条件 R2e が時刻 s + 1 で 注意喚起(require attention) とは
s
s
s
{e}B
s (x2e ) ' 0 & r2e = 0(8)となっていること。
これが Bs , 2e の代わりに As , 2e + 1 で成立するとき、R2e+1 が時刻 s + 1
で注意喚起と呼ぶ。
時刻 s + 1 での定め方：

1. i ≤ s なるどの i についても Ri が s + 1 で注意喚起でないとき：何もしない、つまりどんな e についても
As+1 = As , Bs+1 = Bs , xs+1
= xse , res+1 = res .
e2. ある i ≤ s について Ri が s + 1 で注意喚起であるとき：そのような最小の i を取る。i = 2e とする（i = 2e + 1 なら以下で、A と B の役割を交換する）。
(a)s+1
sAs+1 := As ∪ {xs2e }, Bs+1 = Bs , xs+1
2e = x2e , r2e := 1.

(b) R2e より高い優先度の Rj (j < 2e) については変更しない：
xs+1= xsj , rjs+1 = rjs .
j(c) R2e より低い優先度の Rj (j > 2e) については設定し直す：
xs+1:= hs + 1, ji > s, rjs+1 := 0.
j
構成から分かる通り (7) が充たされ、よってy ∈ As ∪ Bs ⇒ max{(y)0 , (y)1 } < s

(9)

まとめ

1. xse が t > s で変化するのは、ある Ri (i < e) が t で注意喚起される場合に限る。
2. res = 1 が t > s で ret = 0 となるのは、ある Ri (i < e) が t で注意喚起される場合に限る。
3. x2e = hy, 2ei ∈ A なのは、ある s > y で R2e が注意喚起される場合に限る。
4. Ri が s で注意喚起になる最小の i ≤ s で 2e > i ならば、xs2e = hs, 2ei,
s
r2e
= 0.
9

まとめ

1. xse が t > s で変化するのは、ある Ri (i < e) が t で注意喚起される場合に限る。
2. res = 1 が t > s で ret = 0 となるのは、ある Ri (i < e) が t で注意喚起される場合に限る。
3. x2e = hy, 2ei ∈ A なのは、ある s > y で R2e が注意喚起される場合に限る。
4. Ri が s で注意喚起になる最小の i ≤ s で 2e > i ならば、xs2e = hs, 2ei,
s
r2e
= 0.
補題 4.2 どの条件 Ri も高々有限個の時刻でしか注意喚起されない。
S
S
従って極限 xi = lims→∞ xsi が定義され、xi が A = s As , B = s Bs に関して条件 Ri を満たす。
証明. i に関する帰納法で注意喚起の有限性を示す。各 j < i について Rj はある時刻以降では注意喚起されないから、十分大きい s を取ると、その時刻以降ではどの Rj (j < i) も注意喚起されないとしてよい。s をこれを満たす最小の数とする。先ず t > s ⇒ xti = xsi = xi である。
初めに Ri が t > s で注意喚起されるとしたら u > t ⇒ riu = rit = 1 であるから、そのような機会は高々一回である。よって Ri は有限回しか注意喚起されない。
次に s の最小性より、s > 0 なら時刻 s においてある Rj (j < i) が注意喚起されていたはずなので xi = xsi = hs, ii となり、(9) より

xi 6∈ As ∪ Bs & ris = 0(10)

以下、i = 2e として（i = 2e + 1 も同様）、x2e が R2e を満たすことを見る。
初めに R2e がある t + 1 > s で注意喚起である場合を考える。このとき
utx2e ∈ At+1 ⊆ A で {e}Bt (x2e ) ' 0 だが、j > 2e, u > t について xj > t となっているので (6) B|t = Bt |t であり、よって (2) より {e}B (x2e ) ' 0 とな
り、条件 R2e が充たされる。
次に R2e はどんな t + 1 > s でも注意喚起されない場合を考える。すると
tt(10) より x2e 6∈ A となり、また r2e= 0 より {e}Bt (x2e ) 6' 0 なので（' 0
なら R2e が t + 1 で注意喚起になる）(2) より {e}B (x2e ) 6' 0 となり、この場合も条件 R2e が充たされる。
2

10

参考文献
[1] J. R. Shoenfield, Recursion Theory, Lecture Notes in Logic vol. 1(1993),
Springer.
[2] R. I. Soare, Recursively Enumerable Sets and Degrees, Perspective inMathematical logic(1987), Springer.

11