Can a semi-decidable problem be also decidable?
-
30-10-2019 - |
Question
As far as I understand, a semi-decidable (recursively enumerable)
problem could be:
- decidable (recursive) or
- undecidable (nonrecursively enumerable)
This post made me wonder if this is not conventionally followed. This is my answer to it and as far as I understand it is correct:
A semidecidable problem (or equivalently a recursively enumerable problem) could be:
Decidable: If the problem and its complement are both semidecidable (or recursively enumerable), then the problem is decidable (recursive).
Undecidable: If the problem is semidecidable and its complement is not semidecidable (that is, is not recursively enumerable).
Important note: Remember that a decidable (recursive) problem is also semidecidable (recursively enumerable). Conversely, if a problem is not recursively enumerable (semidecidable), then is not recursive (decidable).
What the Wikipedia entry says is that:
Partially decidable problems that are not decidable are called undecidable.
In general, a semidecidable problem (recursively enumerable) could be decidable (recursive) or undecidable (nonrecursively enumerable).
Also note that a problem and its complement could both (or just one of them) be not even semi-decidable (nonrecursively enumerable). Also note that, if a problem is recursive, its complement is also recursive.
Is it conventionally (always) understood this way? Is there some literature that presents semi-decidability (partially decidable, recursively enumerable) problem as an equivalent of undecidability?
No correct solution