ライス＝シャピロの定理のソースを表示

[[再帰理論|計算可能性理論]]において、'''ライス＝シャピロの定理'''（{{lang-en-short|Rice-Shapiro theorem}}）とは[[ライスの定理]]の一般化した定理である。名称は Henry Gordon Rice と Norman Shapiro に因む。<ref>{{ cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley  | publisher=MIT Press|isbn=0-262-68052-1 | year=1987}}</ref>

==非形式的な言明==
<!--
The statement can be expressed informally as follows: given that a [[computable function]] (viewed as a black-box) is an infinite object{{clarification needed|date=September 2013|Requiring infinite information to specify? Some infinite set?}}, and given that we cannot hope to develop a general algorithm for studying a property of the function on infinite input-output pairs, there is in general no truly better way than to apply the function on some inputs and hope to get their outputs.{{citation needed|reason=The interpretation of an authority is needed here|date=January 2014}}
-->
定理の主張は非形式的には次のように述べられる： 計算可能関数の半決定可能な述語 ''A'' と、計算可能関数 ''f'' が与えられたとき、 ''f'' が ''A'' を満たす為には、''f'' の有限部分で ''A'' を満たすものが存在することが必要十分である。いま ''f'' が ''A'' を満たしていると仮定しよう。するとライス＝シャピロの定理より ''f'' の有限部分 ''g'' が存在して ''A'' を満たす。このとき ''g'' の任意の計算可能な延長関数もまた ''A'' を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。

==形式的な言明==
いま ''A'' を（1変数）[[帰納的関数|部分帰納的]]関数の集合で、指標の集合 <math>\mathrm{Index}(A)=\{ e \mid \varphi_e \in A \}</math> が[[帰納的可算]]であるものとする。ここに <math>\varphi</math> は部分帰納的関数の[[ナンバリング_(計算可能性理論)|アクセプタブル・ナンバリング]]である。

このとき任意の部分帰納的関数 <math>\psi</math> について、次は同値：
* <math>\psi \in A</math>;
* 有限関数 <math>\theta</math> で <math>\theta \subseteq \psi</math> かつ <math>\theta \in A</math> なるものが存在する。

ここで有限関数とは有限な定義域を持つ部分関数をいう。また <math>\theta \subseteq \psi</math> とは <math>\theta</math> の定義域で <math>\theta(x) = \psi(x)</math> が成り立つこと（<math>\theta</math> が <math>\psi</math> の制限であること）をいう。

一般に、次の主張が成り立つ： 集合 <math>\mathrm{Index}(A)</math> が帰納的可算であることと、次の2つの条件を満たすこととは同値である：

* <math>\{c(\theta): \theta : \mbox{finite} \wedge \theta \in A\}</math> は帰納的可算;
* <math>n \in A</math> であることと、有限関数 <math>\theta</math> で <math>\theta \subseteq \varphi_n</math> かつ <math>\theta \in A</math> なるものが存在することとは同値。ここで <math>c(\theta)</math> は <math>\theta</math> の標準的な指標である。

==証明==
''A'' を部分帰納的関数の集合で、指標の集合 <math>\mathrm{Index}(A)</math> が帰納的可算であるものとする。

まず ''f'' が ''A'' に属す部分帰納的関数で、''f'' のいかなる有限部分関数も ''A'' に属さないと仮定する。帰納的でない帰納的可算集合 <math>W_e</math> を取る（例えば <math>W_e</math> として[[停止性問題]]の対角線を取ればよい）。次の部分帰納的関数を考える：

<math>
g(x, y) = \begin{cases}
\uparrow & x \in W_{e, y}\\
f(y) & \mbox{otherwise}
\end{cases}
</math>

ここで <math>W_{e,y}</math> は有限集合の帰納的な増大列で <math>\lim W_{e,y} = W_e</math> が成り立つようなものとする。[[smn定理]]より <math>\varphi_{h(x)}(y) = g(x, y)</math> なる全域帰納的関数 ''h'' が存在する。明らかに <math>\varphi_{h(x)}\subseteq f</math> が成り立つ。次の2つの場合が考えられる：
* <math>x</math> が <math>W_e</math> に属すとき： <math>x \in W_{e, y} \mbox{ a.e. }y</math> が成り立つ。したがって <math>g(x, y) = \varphi_{h(x)}</math> の定義域は有限である。仮定より ''f'' のいかなる有限部分も ''A'' に属さないから、<math>h(x) \notin \mathrm{Index}(A)</math> が成り立つ。
* <math>x</math> が <math>W_e</math> に属さないとき： <math>x \notin W_{e, y}</math> が任意の ''y'' で成り立つ。したがって <math>\varphi_{h(x)} = f</math> が成り立つ。仮定より ''f'' は ''A'' に属すから、<math>h(x) \in \mathrm{Index}(A)</math> が成り立つ。
したがって <math>\mathbb{N} \setminus W_e</math> は <math>\mathrm{Index}(A)</math> に[[多対一還元]]可能である。 <math>\mathrm{Index}(A)</math> は帰納的可算であるから、 <math>\mathbb{N} \setminus W_e</math> も帰納的可算である。これは <math>W_e</math> の取り方に反する。

次に ''f'' を ''A'' に属さない部分帰納的関数で、 ''f'' の有限部分 ''g'' で ''A'' に属すものが存在すると仮定する。帰納的でない帰納的可算集合 <math>W_e</math> を取る。次の部分帰納的関数を考える：

<math>
h(x, y) = \begin{cases}
f(y) & g(y)\downarrow \mbox{ or } x \in W_e \\
\uparrow & \mbox{otherwise}
\end{cases}
</math>

[[smn定理]]より <math>\varphi_{k(x)}(y) = h(x, y)</math> なる全域帰納的関数 ''k'' が存在する。明らかに <math>\varphi_{k(x)}\subseteq  f</math> が成り立つ。次の2つの場合が考えられる：
* <math>x</math> が <math>W_e</math> に属すとき： <math>\varphi_{k(x)} = f</math> が成り立つ。仮定より ''f'' は ''A'' に属さないから、 <math>k(x) \notin \mathrm{Index}(A)</math> が成り立つ。
* <math>x</math> が <math>W_e</math> に属さないとき： <math>\varphi_{k(x)} = g</math> が成り立つ。仮定より ''g'' は ''A'' に属すから、 <math>k(x) \in \mathrm{Index}(A)</math> が成り立つ。
したがって <math>\mathbb{N} \setminus W_e</math> は <math>\mathrm{Index}(A)</math> に多対一還元可能である。 <math>\mathrm{Index}(A)</math> は帰納的可算であるから、 <math>\mathbb{N} \setminus W_e</math> も帰納的可算である。これは <math>W_e</math> の取り方に反する。

==ライスの定理の導出==
ライス＝シャピロの定理はライスの定理の一般化となっている。 ''A'' を部分帰納的関数の集合で、指標の集合 <math>\mathrm{Index}(A)</math> が[[決定可能|帰納的]]であるものとする。''A'' が空な関数を含むならば、ライス＝シャピロの定理より ''A'' は部分帰納的関数全体に一致する。 ''A'' が空な関数を含まないならば、補集合がそれを含むから、ライス＝シャピロの定理より ''A'' の補集合が部分帰納的関数全体に一致する。これはライスの定理の主張にほかならない。

==注釈==
{{reflist}}

==参考文献==
*{{cite book | title=Computability: an introduction to recursive function theory| author=Cutland, Nigel | publisher=Cambridge University Press | year=1980 }}; Theorem 7-2.16.
*{{cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley  | publisher=MIT Press|isbn=0-262-68052-1 | pages=482 | year=1987}}
*{{cite book | title=Classical Recursion Theory| author = Odifreddi, Piergiorgio | publisher = North Holland | year=1989}}

==関連項目==
*[[ライスの定理]]

{{DEFAULTSORT:らいすしやひろのていり}}
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]


{{comp-stub}}