決定可能の半分版

x\in\alphaのときのみ答えを返す

集合\alphaを半決定するプログラムが存在するとき、

\alphaは半決定可能である、と言う

このような集合のことを半決定可能集合と言う

以下のようなプログラムQを、「\alphaを半決定するプログラム」と言う

1入力プログラムQを入力xで実行した場合、集合\alphaに対して

x\in\alphaの場合は1を返して実行を終了し、

x\notin\alphaの場合は実行が終了しない

定理 ref p.113

集合\alphaに関する以下の2条件は同値である

\alphaは決定可能である

\alphaと\bar{\alpha}はともに半決定可能である