チューリングマシンの停止性定理

 投稿者：永野護  投稿日：2011年 8月19日(金)16時22分36秒
  計算量の理論の本を読んでいたら、チューリングマシンの停止性定理
というのがでており、任意のプログラムの実行が有限時間で解を出力して終了するか
いつまでたっても計算が終了しないかを判定するアルゴリズムは存在しない
、というようなことが書かれていたのですが、たとえば

------------------------------------------------------------
FOR  a=1  TO   1000
IF   a^2=25  THEN  PRINT   a  :  STOP
NEXT   a
END
-----------------------------------------------------------------
というプログラムであれば明らかにa=5を出力して停止すると
思われますが、チューリングマシンの停止性定理というのは
任意のプログラムを判定できるとは限らないということを
いっているのであり、私が上で例示したプログラムの場合は
停止すると判定できる、ということでよいでしょうか。
まったく素人で恥ずかしいのですが、恥を忍んでの質問です。
よろしくお願いします。残暑の厳しい折です。皆様のご健康を
お祈りいたします。 		 

Re: チューリングマシンの停止性定理

 投稿者：白石和夫  投稿日：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

の形だったら，どんなアルゴリズムを用いればいいのでしょうか。
（現実のコンピュータは扱うことが可能な数値の範囲が制限されますが，そのような制限はないものとします）



 		 

Re: チューリングマシンの停止性定理

 投稿者：白石和夫  投稿日：2011年 8月20日(土)08時19分36秒
  > No.1646[元記事へ]

要するに，
「任意のプログラムを判定することはできない」
のではなく，
「任意のプログラムを判定することのできるプログラムは作れない」
です。
 		 

チューリングマシンの停止性定理

 投稿者：永野護  投稿日：2011年 8月20日(土)10時35分23秒
  わかりやすい回答ありがとうございました。
お手数をおかけしました。
敬具
 		 

戻る