|
投稿者：永野護
投稿日：2011年 8月19日(金)16時22分36秒
|
|
|
|
計算量の理論の本を読んでいたら、チューリングマシンの停止性定理
というのがでており、任意のプログラムの実行が有限時間で解を出力して終了するか
いつまでたっても計算が終了しないかを判定するアルゴリズムは存在しない
、というようなことが書かれていたのですが、たとえば
------------------------------------------------------------
FOR a=1 TO 1000
IF a^2=25 THEN PRINT a : STOP
NEXT a
END
-----------------------------------------------------------------
というプログラムであれば明らかにa=5を出力して停止すると
思われますが、チューリングマシンの停止性定理というのは
任意のプログラムを判定できるとは限らないということを
いっているのであり、私が上で例示したプログラムの場合は
停止すると判定できる、ということでよいでしょうか。
まったく素人で恥ずかしいのですが、恥を忍んでの質問です。
よろしくお願いします。残暑の厳しい折です。皆様のご健康を
お祈りいたします。
|
|
|
|
投稿者：白石和夫
投稿日：2011年 8月19日(金)18時20分37秒
|
|
|
|
FOR a=1 to 1000
○○○○
NEXT a
は，途中でaの値を変えることがない限り必ず停止するので，○○○○ が無限ループを含まなければ必ず停止します。それではおもしろくないので，
LET a=1
DO
IF a^2=25 THEN
PRINT a
EXIT DO
END IF
LET a=a+1
LOOP
END
の停止性を判定する問題にしてみます。
このプログラムだけを対象するする場合のアルゴリズムは，
PRINT "Yes"
END
でいいので，これもつまらない問題です。
そこで，
LET a=1
DO
IF a^2 = □ THEN
PRINT a
EXIT DO
END IF
LET a=a+1
LOOP
END
の型のプログラムの停止性を考えます。
この問題は，□ が平方数か否かを判定するアルゴリズムが存在するかどうかの問題になります。
そのようなアルゴリズムは実際に存在します。
たとえば，
INPUT n
LET a=1
DO UNTIL a^2>=n
LET a=a+1
LOOP
IF a^2=n THEN PRINT "平方数" ELSE PRINT "平方数でない"
END
それでは，対象となるプログラムが，
DEF f(x)=◇◇◇
LET a=1
DO
IF f(a) = 25 THEN
PRINT a
EXIT DO
END IF
LET a=a+1
LOOP
END
の形だったら，どんなアルゴリズムを用いればいいのでしょうか。
（現実のコンピュータは扱うことが可能な数値の範囲が制限されますが，そのような制限はないものとします）
|
|
|
|
投稿者：白石和夫
投稿日：2011年 8月20日(土)08時19分36秒
|
|
|
|
> No.1646[元記事へ]
要するに，
「任意のプログラムを判定することはできない」
のではなく，
「任意のプログラムを判定することのできるプログラムは作れない」
です。
|
|
|
|
投稿者：永野護
投稿日：2011年 8月20日(土)10時35分23秒
|
|
|
|
わかりやすい回答ありがとうございました。
お手数をおかけしました。
敬具
|
|
|
戻る