Computability
An arbitrary set M is:
- decidable
- if an algorithm exists that decides
for every x whether x∈M or x∉M.
In other words, if the property of its consistency or inconsistency is determinable.
M is decidable ⇔ ΧM is computable.
Where ΧM(x) = {1 if x∈M, 0 if x∉M} is the characteristic function of M.
- undecidable
- if M is not decidable.
- semi-decidable
- if an algorithm exists that decides
for every x∈M that x∈M.
For those x∉M, the algorithm does not even need to terminate.
Another terminus for this property is recursively enumerable.
M is semi-decidable ⇔ Χ'M is computable.
Where ΧM'(x) = {1 if x∈M, ⊥ if x∉M} is the semi-characteristic function of M.