patternMinor
Can a semi-decidable problem be also decidable?
Viewed 0 times
problemcansemialsodecidable
Problem
As far as I understand, a
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?
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?
Solution
Yes, a recursively enumerable language may be either decidable or undecidable. To see this, you ust look at the definitions of the terms.
A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-decidable) if there is a Turing machine that halts and accepts any input in $L$ and, for any input not in $L$, it either halts and rejects or it does not halt.
Therefore, every recursive language is recursively enumerable. The machine that decides the recursive language is a special case of the machine required for a recursively enumerable language: specifically, it is allowed to either loop forever or reject for words not in $L$; in fact, it always rejects and never uses the option of looping forever.
A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-decidable) if there is a Turing machine that halts and accepts any input in $L$ and, for any input not in $L$, it either halts and rejects or it does not halt.
Therefore, every recursive language is recursively enumerable. The machine that decides the recursive language is a special case of the machine required for a recursively enumerable language: specifically, it is allowed to either loop forever or reject for words not in $L$; in fact, it always rejects and never uses the option of looping forever.
Context
StackExchange Computer Science Q#19641, answer score: 9
Revisions (0)
No revisions yet.