理論が半決定可能であるとは、任意の論理式を与えられたとき、その論理式がその理論に含まれる場合は正しい答を出せる実効的方法があるが、その理論に含まれない論理式の場合は答を出せない可能性があることを言う。