概念導讀
決定問題：在明示有限輸入集上證明試除程序是 decider
取輸入集合 X={0,1,2,3,4,5,6,7,8,9}、規格 P(x)：「x 是質數」與 yes-instance 集合 Y={x∈X ∣ P(x)}。在明示的 while 程式計算模型 W 中，證明試除程序 D1 對每個 x∈X 都終止，且 D1(x)=true 當且僅當 x∈Y，因此 D1 是 (X,Y) 的 decider；再說明只在 yes-instance 上停止的 D2 與只看奇偶的 D3 都不是 decider。