停止性問題についてまとめておく

Wikiがわかりやすかった。
停止性問題 - Wikipedia

まず、プログラムが停止するかどうかを判別できるプログラムH(A)が存在したと仮定する。(この仮定が結果的に矛盾を生じる)
プログラムH(A)は引数としてプログラムAを取り、プログラムAが停止する場合はYESを、停止しない場合はNOを返す。

次に、プログラムHを利用して次のようなプログラムM(H, A)を考える。

M(H, A){
    if(H(A) == YES){
        while(1);
    }
}

上の実装を見るとわかるが、M(H, A)はH(A)がYESを返す(つまり、Aが停止するとHが判断する場合)に無限ループに入り、M(H, A)はH(A)がNOを返す(つまり、Aが停止しないとHが判断する場合)に停止する。
ここで問題、M(H, M)は停止するだろうか？

M(H, M){
    if(H(M) == YES){
        while(1);
    }
}

【M(H, M)が停止する場合】
M(H, M)が停止するということは、if文の中の「H(M) == YES」が成り立たなかった場合である。つまり、H(M)はNOを返した。
Hは引数のプログラムが停止する場合はYES、停止しない場合はNOを返すので、Mは停止しないことになる。
これは、Mが停止するという結果に矛盾。

【M(H, M)が停止しない場合】
M(H, M)が停止しないということは、if文の中の「H(M) == YES」が成り立った場合である。つまり、H(M)はYESを返した。
Hは引数のプログラムが停止する場合はYES、停止しない場合はNOを返すので、Mは停止することになる。
これは、Mが停止しないという結果に矛盾。

よって、そのようなプログラムHは存在しない。