「決定可能」はなぜアルゴリズムを先に決めるの?
授業で，ある問題が決定可能であることの定義は
であって，
ではない，と説明しました．
一階述語論理で表現すると，
- 正しい: ∃A [∀p∈P [solve(A, p)] ]
- 間違い: ∀p∈P [∃A [solve(A, p)] ]
となります．Pが問題，∃Aが「アルゴリズムが存在して」，∀p∈Pが「問題に属する任意の個別問題」，solve(A, p)が「個別問題pはアルゴリズムAで解ける」にそれぞれ対応付けられます．本当はAにも範囲があるのですが，ここでは割愛します．
さて，なぜ前者が正しく後者が間違いなのかというと，「決定不能の証明をしやすくするため，このように取り決めた(このように決定可能性を定義した)」というのが一番大きな理由です．決定可能でなければ決定不能ということなので*1，上の正しいと間違いのそれぞれを，否定してみましょう．
- 正しい決定不能: ¬∃A [∀p∈P [solve(A, p)] ] = ∀A [∃p∈P [¬solve(A, p)] ]
- 間違いの決定不能: ¬∀p∈P [∃A [solve(A, p)] ] = ∃p∈P [∀A [¬solve(A, p)] ]
正しい決定不能の論理式は，停止性問題の証明でよく見かけます．たいてい，背理法を使って，「停止性問題を解くアルゴリズムが存在すれば，そのアルゴリズムを使って，肯定的にも否定的にも判定することのできない個別問題を作ることができる」としていますが，実際には「(停止性問題を解くという)任意のアルゴリズムに対して，そのアルゴリズムを使って，肯定的にも否定的にも判定することのできない個別問題を作ることができる」を証明しているのです．
間違いの決定不能について，この形で論理式が真であることを証明できたとして，その証明や結果をどのように生かすかが明確ではありません．
これは，よく「一般に決定不能」と呼ばれることと密接な関係があります．考えている問題が一般的すぎて(取り得る入力の範囲が広すぎて)，その問題の中の個別問題をすべて解くことのできる，救世主的なアルゴリズムは存在しない，というのが，直感的なイメージです．
そしてこのイメージをさらに進めると，「広すぎるとダメだけど，ある程度狭めたら，解けるんじゃないか?」という疑問が起こります．この考え方は健全で，実際，対象としている問題が決定不能なことを証明した上で，決定可能な部分問題a partial problem which is decidableを見つけ，本当に対象としている範囲がそこに含まれていることを指摘すれば，一つの論文になることもあります．
実際のところ，Pという「個別問題の集合」で見ると大きいですが*2，個別問題一つ一つで見ると十分小さくかつ具体的で，それぞれに応じたアルゴリズムというのが立てられるかもしれません．結局のところ，「∃p∈P [∀A [¬solve(A, p)] ]」は実用的な多くの問題に対して偽になると予想され，この論理式でもって決定不能とするのは，実用の面でまずいということです．
なお，途中で「救世主的なアルゴリズム」というのを挙げましたが，(正しい)決定可能性の証明にあたっては，単一のアルゴリズムでなくてもかまいません．
すなわち，問題Pをいくつかに分割して，それぞれで異なる解き方(アルゴリズム)を適用させても，いいのです．
ただし，それでOKとするには，いくつか条件がつきます．問題Pの分割は有限個でなければなりません．それと，どのアルゴリズムを適用するかの判定は，有限時間内で行われないといけません．
これらの条件を満たせば*3，全体として，問題Pを解くアルゴリズムが構成されるということになります．これは，救世主を「一人の人」と見るか，「複数人のグループ」と見るかの違いと言えそうです．
