I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability.

  1. Decidable: A language $L$ (a set of strings) is decidable if there exists a Turing machine $M$ that, for any input string $w$, halts on w and correctly decides whether $w$ belongs to $L$ or not. In other words, for any input $w$, $M$ will either accept or reject $w$, and it will always provide a definite answer in a finite amount of time.
  2. Semi-decidable: A language $L$ is semi-decidable if there exists a Turing machine $M$ that, for any input string $w$, halts and accepts $w$ if w belongs to $L$. However, if $w$ does not belong to $L$, $M$ may run forever without halting, or it may reject $w$. In other words, it can recognize members of $L$, but it may not necessarily reject non-members.
  3. Undecidable: A language $L$ is undecidable if there is no Turing machine that can decide whether any given input string $w$ belongs to $L$ or not. In other words, there is no algorithm that can always provide a correct yes-or-no answer for membership in $L$.
  4. Not semi-decidable: This term refers to languages or problems for which there is no Turing machine that can recognize all members of the language, meaning there is no Turing machine that will halt and accept all strings in the language, and some strings in the language may cause the machine to run forever without halting.
  5. Not decidable: Is this the same as undecidable? Or does it specifically imply that it is not decidable but we cannot make a statement on whether a language $L$ is semi-decidable or not.

The main issue I have is the difference between undecidable and not decidable languages. For example, we have the special Halting Problem: $$K := \{w ∈ \{0, 1\}^∗| w\#w ∈ H\}$$ where $H$ is the general Halting Problem. Now the problem is that we know that $K$ is undecidable. Is it the same as saying that $K$ is not decidable?

This problem might seem basic, but because both terms are used I would appreciate some clarification on this.


1 Answer 1


Undecidable means "not decidable". They are synonyms. The definition is: we say that $L$ is undecidable if $L$ is not decidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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