計算可能性理論 において、ライス＝シャピロの定理 （英 : 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)}
{
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}
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}
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 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 関連項目 [ 編集 ]
