計算可能性理論 において、ライス=シャピロの定理 (英 : Rice-Shapiro theorem )とはライスの定理 の一般化した定理である。名称は Henry Gordon Rice と Norman Shapiro に因む。[1]
非形式的な言明 [ 編集 ]
定理の主張は非形式的には次のように述べられる: 計算可能関数の半決定可能な述語 A と、計算可能関数 f が与えられたとき、 f が A を満たす為には、f の有限部分で A を満たすものが存在することが必要十分である。いま f が A を満たしていると仮定しよう。するとライス=シャピロの定理より f の有限部分 g が存在して A を満たす。このとき g の任意の計算可能な延長関数もまた A を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。
形式的な言明 [ 編集 ]
いま A を(1変数)部分帰納的 関数の集合で、指標の集合
I
n
d
e
x
(
A
)
=
{
e
∣
φ
e
∈
A
}
{\displaystyle \mathrm {Index} (A)=\{e\mid \varphi _{e}\in A\}}
が帰納的可算 であるものとする。ここに
φ
{\displaystyle \varphi }
は部分帰納的関数のアクセプタブル・ナンバリング である。
このとき任意の部分帰納的関数
ψ
{\displaystyle \psi }
について、次は同値:
ψ
∈
A
{\displaystyle \psi \in A}
;
有限関数
θ
{\displaystyle \theta }
で
θ
⊆
ψ
{\displaystyle \theta \subseteq \psi }
かつ
θ
∈
A
{\displaystyle \theta \in A}
なるものが存在する。
ここで有限関数とは有限な定義域を持つ部分関数をいう。また
θ
⊆
ψ
{\displaystyle \theta \subseteq \psi }
とは
θ
{\displaystyle \theta }
の定義域で
θ
(
x
)
=
ψ
(
x
)
{\displaystyle \theta (x)=\psi (x)}
が成り立つこと(
θ
{\displaystyle \theta }
が
ψ
{\displaystyle \psi }
の制限であること)をいう。
一般に、次の主張が成り立つ: 集合
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
が帰納的可算であることと、次の2つの条件を満たすこととは同値である:
{
c
(
θ
)
:
θ
:
finite
∧
θ
∈
A
}
{\displaystyle \{c(\theta ):\theta :{\mbox{finite}}\wedge \theta \in A\}}
は帰納的可算;
n
∈
A
{\displaystyle n\in A}
であることと、有限関数
θ
{\displaystyle \theta }
で
θ
⊆
φ
n
{\displaystyle \theta \subseteq \varphi _{n}}
かつ
θ
∈
A
{\displaystyle \theta \in A}
なるものが存在することとは同値。ここで
c
(
θ
)
{\displaystyle c(\theta )}
は
θ
{\displaystyle \theta }
の標準的な指標である。
A を部分帰納的関数の集合で、指標の集合
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
が帰納的可算であるものとする。
まず f が A に属す部分帰納的関数で、f のいかなる有限部分関数も A に属さないと仮定する。帰納的でない帰納的可算集合
W
e
{\displaystyle W_{e}}
を取る(例えば
W
e
{\displaystyle W_{e}}
として停止性問題 の対角線を取ればよい)。次の部分帰納的関数を考える:
g
(
x
,
y
)
=
{
↑
x
∈
W
e
,
y
f
(
y
)
otherwise
{\displaystyle g(x,y)={\begin{cases}\uparrow &x\in W_{e,y}\\f(y)&{\mbox{otherwise}}\end{cases}}}
ここで
W
e
,
y
{\displaystyle W_{e,y}}
は有限集合の帰納的な増大列で
lim
W
e
,
y
=
W
e
{\displaystyle \lim W_{e,y}=W_{e}}
が成り立つようなものとする。smn定理 より
φ
h
(
x
)
(
y
)
=
g
(
x
,
y
)
{\displaystyle \varphi _{h(x)}(y)=g(x,y)}
なる全域帰納的関数 h が存在する。明らかに
φ
h
(
x
)
⊆
f
{\displaystyle \varphi _{h(x)}\subseteq f}
が成り立つ。次の2つの場合が考えられる:
x
{\displaystyle x}
が
W
e
{\displaystyle W_{e}}
に属すとき:
x
∈
W
e
,
y
a.e.
y
{\displaystyle x\in W_{e,y}{\mbox{ a.e. }}y}
が成り立つ。したがって
g
(
x
,
y
)
=
φ
h
(
x
)
{\displaystyle g(x,y)=\varphi _{h(x)}}
の定義域は有限である。仮定より f のいかなる有限部分も A に属さないから、
h
(
x
)
∉
I
n
d
e
x
(
A
)
{\displaystyle h(x)\notin \mathrm {Index} (A)}
が成り立つ。
x
{\displaystyle x}
が
W
e
{\displaystyle W_{e}}
に属さないとき:
x
∉
W
e
,
y
{\displaystyle x\notin W_{e,y}}
が任意の y で成り立つ。したがって
φ
h
(
x
)
=
f
{\displaystyle \varphi _{h(x)}=f}
が成り立つ。仮定より f は A に属すから、
h
(
x
)
∈
I
n
d
e
x
(
A
)
{\displaystyle h(x)\in \mathrm {Index} (A)}
が成り立つ。
したがって
N
∖
W
e
{\displaystyle \mathbb {N} \setminus W_{e}}
は
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
に多対一還元 可能である。
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
は帰納的可算であるから、
N
∖
W
e
{\displaystyle \mathbb {N} \setminus W_{e}}
も帰納的可算である。これは
W
e
{\displaystyle W_{e}}
の取り方に反する。
次に f を A に属さない部分帰納的関数で、 f の有限部分 g で A に属すものが存在すると仮定する。帰納的でない帰納的可算集合
W
e
{\displaystyle W_{e}}
を取る。次の部分帰納的関数を考える:
h
(
x
,
y
)
=
{
f
(
y
)
g
(
y
)
↓
or
x
∈
W
e
↑
otherwise
{\displaystyle h(x,y)={\begin{cases}f(y)&g(y)\downarrow {\mbox{ or }}x\in W_{e}\\\uparrow &{\mbox{otherwise}}\end{cases}}}
smn定理 より
φ
k
(
x
)
(
y
)
=
h
(
x
,
y
)
{\displaystyle \varphi _{k(x)}(y)=h(x,y)}
なる全域帰納的関数 k が存在する。明らかに
φ
k
(
x
)
⊆
f
{\displaystyle \varphi _{k(x)}\subseteq f}
が成り立つ。次の2つの場合が考えられる:
x
{\displaystyle x}
が
W
e
{\displaystyle W_{e}}
に属すとき:
φ
k
(
x
)
=
f
{\displaystyle \varphi _{k(x)}=f}
が成り立つ。仮定より f は A に属さないから、
k
(
x
)
∉
I
n
d
e
x
(
A
)
{\displaystyle k(x)\notin \mathrm {Index} (A)}
が成り立つ。
x
{\displaystyle x}
が
W
e
{\displaystyle W_{e}}
に属さないとき:
φ
k
(
x
)
=
g
{\displaystyle \varphi _{k(x)}=g}
が成り立つ。仮定より g は A に属すから、
k
(
x
)
∈
I
n
d
e
x
(
A
)
{\displaystyle k(x)\in \mathrm {Index} (A)}
が成り立つ。
したがって
N
∖
W
e
{\displaystyle \mathbb {N} \setminus W_{e}}
は
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
に多対一還元可能である。
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
は帰納的可算であるから、
N
∖
W
e
{\displaystyle \mathbb {N} \setminus W_{e}}
も帰納的可算である。これは
W
e
{\displaystyle W_{e}}
の取り方に反する。
ライスの定理の導出 [ 編集 ]
ライス=シャピロの定理はライスの定理の一般化となっている。 A を部分帰納的関数の集合で、指標の集合
I
n
d
e
x
(
A
)
{\displaystyle \mathrm {Index} (A)}
が帰納的 であるものとする。A が空な関数を含むならば、ライス=シャピロの定理より A は部分帰納的関数全体に一致する。 A が空な関数を含まないならば、補集合がそれを含むから、ライス=シャピロの定理より A の補集合が部分帰納的関数全体に一致する。これはライスの定理の主張にほかならない。
^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability . MIT Press. ISBN 0-262-68052-1
参考文献 [ 編集 ]
Cutland, Nigel (1980). Computability: an introduction to recursive function theory . Cambridge University Press ; Theorem 7-2.16.
Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability . MIT Press. pp. 482. ISBN 0-262-68052-1
Odifreddi, Piergiorgio (1989). Classical Recursion Theory . North Holland
関連項目 [ 編集 ]