-
@ThothChildren
- 2018.12.2
- PV 153
ライスの定理
ー 概要 ー
「プログラムAがある性質Fを持つかどうかが自明でないときそれを判定できるプログラムは存在しない」ことを示す定理.このライスの定理はチューリングマシンの停止性問題を一般化したものになっている.
この章を学ぶ前に必要な知識
ポイント
- ライスの定理は、「停止性問題」の一般化
- プログラムAが自明でないある性質Fを持つかどうかを判定できるプログラムは存在しない
- ここでいう性質はプログラムが作成している関数の性質であって、プログラムの行数等は含まないことに注意
解 説
「プログラムAが自明でないある性質Fを持つかどうかを判定できるプログラムは存在しない」ことを示す定理.
ここでいう性質Fというのは関数の表面上の性質を表しており、
・常に0を返す
・10以下の数を返す
などであって、
・プログラムが10行以内である
といったプログラム自身の記述の性質を指すものではないことに注意. | ライスの定理とは |
ライスの定理はチューリングマシンの停止性問題を一般化したものになっている.
具体的には、性質Fを「停止性」としたときに
ライスの定理によれば
「プログラムが"停止性をもつかどうか"を判定するプログラムは存在しない」
ということになり、停止性問題と一致する. | チューリングマシンの停止性問題 |
この章を学んで新たに学べる
Comments
Reasons
知識: チューリングマシンの停止性問題
停止性問題は、任意のプログラムが任意の入力が与えられて停止するかどうかを判定するプログラムは存在するかに関する問題.存在しないことが背理法によって示すことが可能.