決定可能集合
集合
$ \alpha
の
集合の特性関数
が
計算可能
であるとき、
$ \alpha
は計算可能である、または
決定可能
である、という
言い換えると、「なんらかの要素
$ x
」が「
$ \alpha
に含まれるかどうか」が計算可能であれば、
$ \alpha
は決定可能集合