- 361 名前：１３２人目の素数さん [2024/05/05(日) 23:29:55.71 ID:HvNo6+XN.net]
- ご参考
”結論:多くのプログラム言語に対して、その言語で書かれたプログラムの停止性は、決定可能ではない”
//www.cs.tsukuba.ac.jp/~kam/lecture/plm2017/
2017年度の『プログラム言語論』亀山幸義筑波大学情報科学
//www.cs.tsukuba.ac.jp/~kam/lecture/plm2017/termination.pdf
講義資料
プログラム言語論亀山幸義筑波大学情報科学類No.4(停止性)
停止性問題
以下の性質を持つプログラムHは存在するか？
・Hは2引数関数である。
・H(P,x)はどんな引数P,xに対しても、有限時間で止まり、yesかnoを返す。
・プログラムPが入力xに対して停止するとき、H(P,x)はyesを返す。
・プログラムPが入力xに対して停止しない(無限ループする)とき、H(P,x)はnoを返す。このようなHが存在するか、という問題が、停止性問題(Halting Problem)である。
・この章では、最終的に、「そのようなHは、存在しない」ことが示される。
第2ステップ:Kを使った推論その1
プログラムKに、引数としてK自身を渡すことを考える。
(Case1)もし、K(K)が停止してyesを返したら、
・Kの定義から、H(K,K)はnoを返す。
・よって、Hの定義から、プログラムKが入力Kに対して停止しない。
・よって、K(K)は停止してyesを返し、かつ、停止しない、ということになり、矛盾である。
(Case2)もし、K(K)が無限ループなら、
・Kの定義から、H(K,K)はyesを返す。
・よって、Hの定義から、プログラムKが入力Kに対して停止する。
・よって、K(K)は無限ループかつ、停止する、ということになり、矛盾である。よって矛盾である。
第3ステップ
結論:多くのプログラム言語に対して、その言語で書かれたプログラムの停止性は、決定可能ではない。
付録:Turing機械とプログラム言語
Turing機械と同等の計算能力を持つプログラム言語や計算モデルは、どんなものでも、停止性問題の解となるものは存在しない。
・(型のない)ラムダ計算の体系帰納的関数の体系
・(理想化された)C言語で書けるプログラム(理想化された)
・OCaml言語で書けるプログラム(理想化された)
・Scheme/Lisp言語で書けるプログラム(理想化された)
・Java言語で書けるプログラム
なお、「Turing機械と同等の計算能力を持つプログラム言語(あるいは計算モデル)」のことをTuringcomplete(チューリングの意味で完全)と呼ぶことがある。
|
 |
