そうみたいですね。
停止問題の方が強いと思ってたんですが、
実際は不完全性定理→停止問題は決定不可能
みたいですね・・・。
あとで証明してみようと思います。

チューリングマシンの停止問題の決定不可能性からRE等への間辺りが
自分の問題意識だったみたいです。