I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability.
- 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.
- 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.
- 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$.
- 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.
- 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.
