前置き

チューリングマシンの停止性問題を証明するn番煎じ記事です
ただ理解できたのがうれしかったので書いた

証明

言葉の定義
停止する → 戻り値を返す or エラーを投げる
停止しない → 無限ループが発生する

関数HOGE(func, x)を以下のように定義する

func(x)が停止する場合   → trueを返す
func(x)が停止しない場合 → falseを返す

関数FUGA(func)を以下のように定義する

HOGE(func, func)がtrue  → FUGA(func)は停止しない
HOGE(func, func)がfalse → FUGA(func)は停止する

以下を考える

FUGA(FUGA)

FUGA(FUGA)が停止する場合

FUGA(FUGA)が停止する = HOGE(FUGA, FUGA)がfalse
                    = FUGA(FUGA)が停止しない（矛盾）

FUGA(FUGA)が停止しない場合

FUGA(FUGA)が停止しない = HOGE(FUGA, FUGA)がtrue
                      = FUGA(FUGA)が停止する（矛盾）

よって関数が停止するか判定する関数HOGEは定義できない

おまけ

JSで表現してみた

// func(x)が停止すればtrue、しなければfalse（大嘘）
function hoge(func, x) {
    try {
        // func(x)が停止するか判定（大嘘）
        eval("func(x)");
    } catch (error) {
        // 握りつぶす
    }
    return true;
}

function fuga(func) {
    if (hoge(func, func)) {
        while (true) {
            console.log("無限ループ")
        }
    }
    console.log("停止")
}

fuga(fuga); // ？！