半決定可能
semi-decidable
$ x\in\alphaのときのみ答えを返す
集合$ \alphaを半決定するプログラムが存在するとき、
$ \alphaは半決定可能である、と言う
以下のようなプログラム$ Qを、「$ \alphaを半決定するプログラム」と言う
1入力プログラム$ Qを入力$ xで実行した場合、集合$ \alphaに対して
$ x\in\alphaの場合は1を返して実行を終了し、
$ x\notin\alphaの場合は実行が終了しない
定理 ref 『C言語による計算の理論』.icon p.113
集合$ \alphaに関する以下の2条件は同値である
$ \alphaと$ \bar{\alpha}はともに半決定可能である