3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 11 '14 at 2:00
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jan 11 '14 at 2:02
  • $\begingroup$ 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. $\endgroup$ – PALEN Jan 11 '14 at 17:53
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer could have been a lot shorter: the point is that recursive languages are a subset of recursively enumerable ones. $\endgroup$ – nbro May 3 '17 at 12:45
  • 2
    $\begingroup$ @nbro To anybody who understands the concepts, it is obvious that every recursive language is RE. It seems, then, that anybody who needs to ask this question does not understand the basic concepts and will benefit from having them explained. I addressed my answer to what I perceived to be the right level; you're welcome to post the obvious answer for people who find the answer obvious but the thing is, they don't really need an answer. $\endgroup$ – David Richerby May 3 '17 at 13:02
  • 1
    $\begingroup$ Fair enough, I would say. My comment above should suffice as a shorter explanation. $\endgroup$ – nbro May 3 '17 at 13:05
  • $\begingroup$ 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" ? $\endgroup$ – Qqwy May 29 at 8:28
  • 1
    $\begingroup$ @Qqwy "Semi-decidable" and "recursively enumerable" mean exactly the same thing. Sets and languages are the same thing: a language is a set of strings and there's no fundamental difference between a set of integers and, e.g., the set of strings that are the decimal encodings of those integers. There must be non-RE languages because there are uncountably many languages but only countably many Turing machines. An example of a non-RE language is the set of strings coding Turing machines that halt on all inputs; another is the complement of the halting problem. $\endgroup$ – David Richerby May 29 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.