Computability
An arbitrary set M is:
- decidable
- if an algorithm exists that decides
for every x whether x in M or x not in 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 in M, 0 if x not in M} is the characteristic function of M.
- undecidable
- if M is not decidable.
- semi-decidable
- if an algorithm exists that decides
for every x in M that x in M.
For those x not in 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 in M, bottom if x not in M} is the semi-characteristic function of M.