# Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be:

1. decidable (recursive) or
2. 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?

• All the definitions you quote are in agreement. They don't present semi-decidability as equivalent to undecidability. Perhaps you're confused by the fact that a decidable problem is a fortiori semi-decidable. – Yuval Filmus Jan 11 '14 at 2:00
• @YuvalFilmus Actually, most of the things quoted (e.g., a language is decidable if it and its complement are RE) are not definitions but theorems. Therein lies the problem: to determine that the statements are indeed all in agreement, one must look at the definitions. – David Richerby Jan 11 '14 at 2:02
• I'm aware of which of the statements are definitions and which ones are theorems that are derived from those definitions. It's just that I recently learned those concepts and well... the wikipedia entry was ambiguous and the accepted StackOverflow answer was wrong (7 upvotes included). Nevermind. I got it right :) I'm accepting the answer. Thank you. – PALEN Jan 11 '14 at 17:53

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.
• Are there semi-decidable languages that are neither decidable nor undedicable? In other words: is "decidable $\cup$ undecidable $=$ semi-decidable" or is "decidable $\cup$ undecidable $\subset$ semi-decidable" ? – Qqwy May 29 '19 at 8:28
• @Qqwy "Undecidable" just means "not decidable", so every language is either decidable or undecidable. However, there are languages that are not semi-decidable, so it's not true that decidable $\cup$ undecidable $\subseteq$ semi-decidable. – David Richerby May 29 '19 at 8:38