ノート:停止性問題

--210.229.215.147 2013年11月3日 (日) 08:14 (UTC)「Hの定義より、Hは入力(A,x)によらず必ず停止する事に注意されたい。A(x)が停止するかどうかを、必ず停止するHを使って決定する事はできない、というのが定理の趣旨である。」についての疑問。[返信]

Aを実行せずに判別する方法があれば、必ず停止するHにも判別することは出来るはずです。

例えば、H(A,x)は、実際、Cの関数だったとしましょう。極端な例ですが、A(x)が

void a(char *x) {
 for(;;){ }
}

であったとすれば、Aが無限ループすることを有限時間内に解析し、終了するHは容易に書けると思います。具体的な解析ロジックまでは思いつきませんが、HはAを実行せず、Aのコードそのものを見る、ということは出来るはずです(便宜上xは無視しています）。

int h( void *a_p , char *x )
{
int result = UNKNOWN;
char *code_p;

    // a_pからコード自体を取り出す。
    for ( mi=0 , code_p=a_p, char c = code_p[mi]; isFuncContinued(c) && mi < MAXSIZE; mi++ )
    {
        // コード解析処理
        if ( endCodeAnalyzed(c,&result) )
        {
           return( result );
        }
    }
    return( result ) ; // コードが長過ぎて判定できない
}
int main(int argc,char **argv)
{
void ( *a )( int );
   h( &a , *argv );
}

Aがプログラムファイルでも等価だとできるのであれば、さらに解析ロジックは容易になると思われます。

つまり、抽象的な言葉では、Hが矛盾するプログラムだということは即座には説明できず、Hが判別できない明らかなコードがあるなら、その条件においてHは停止できなくなる、と証明する必要があると思います。

この問題において、Aが停止するかどうかを、実行しなければならない（少なくともHのプログラムの実行中に）、という前提が疑問です。--以上の署名のないコメントは、210.229.215.174（会話）さんが 2011年8月17日 (水) 16:01 (UTC) に投稿したものです（Louis XX 2011年9月6日 (火) 03:19 (UTC)による付記）。[返信]

実行しなければならない、という前提は特に必要ないと思います。Hそれ自体を引数としてHに与えると、矛盾が導かれるというのが、この証明の言わんとするところではないでしょうか？--220.247.32.2 2013年3月27日 (水) 21:42 (UTC)[返信]

「Aが停止するかどうかを判定するためには、Aを実行しなければならない（少なくともHのプログラムの実行中に）」と考えたのが誤解です。自己適用 M(M) において実行されるのは「外側の M」であり、「内側の M」は（「外側の M」と同じものですが）実行されるわけではありません。--MetaNest（会話） 2013年8月17日 (土) 22:53 (UTC)[返信]

前回署名なしで投稿してしまい大変失礼致しました。私が理解できないのは、「A(x)が停止するかどうかを、必ず停止するHを使って決定する事はできない」という部分です。 Aを実行しなくていいのであれば、なぜHが必ず停止することが問題なのでしょうか。停止性問題を解くHに対し、停止しないプログラムを入力すれば、NO（停止しない）が返るだけです。停止性問題を解くHに対し、自己適用 H(H) すれば、必ずYES（停止する）が返るだけです。停止性問題を解くHは、必ず停止します。停止しないHは定義上存在しません。 Hそれ自体を引数としてHに与えると、矛盾が導かれるというのは、「停止しないHを入力したら」という前提のように思えるのですが。しかし停止するHに、停止しないAを入力し、NO（停止しない）を得ることは可能でしょう（というかそれだけでは不可能と断言はできない）。 --210.229.215.147 2013年11月3日 (日) 08:14 (UTC) lightspeed[返信]

M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとしたとき、M(M)は停止するかどうかを考えてください。「Hそれ自体を引数としてHに与えると、矛盾が導かれる」わけではありません。 TQespr（会話） 2014年2月28日 (金) 21:57 (UTC)[返信]

なんというか、これは文章全体の構成が微妙に誤解を与えてるように感じますね。（私も初見時少し混乱しました）つまり、

1.「停止性問題を解くチューリング機械が存在すると仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾」が生じる

という話があって、その矛盾が生じないようにするには、

2.「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうかを決定せよ」という問題

に対して、

3.「停止性問題を常に正しく解くプログラムは存在しない」という定理

があり、ここで「停止性問題を常に正しく解くプログラム」とは「常に正しく解を決定して停止するプログラム」であり、これが存在する場合1.に挙げた矛盾が生じてしまう。よって、矛盾を生じないようにするには「そのようなプログラムは存在しない」となる、という説明なのですが、

それを説明している「概要」節の中に1.が入っていないので、2.と3.だけ読むと、210.229.215.147さんの様に

「A(x)が停止するかどうかを、必ず停止するHを使って決定する事はできない」という部分が理解できない、「なぜHが必ず停止することが問題なのでしょうか」

という疑問が生じ、混乱してしまうのではないかと感じました。

ちなみに、私は数学専攻でないので上手く修正できませんが、この「停止性問題」について、背理法以外の方法で証明はできないのでしょうか？

（背理法の証明は前提条件の説明が上手くないと一般人に不要の疑問や誤解を与えることが多いように感じられるので・・・）--114.185.148.200 2014年7月14日 (月) 04:30 (UTC)[返信]