I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as follows:

  1. $\text{Special Halting Problem Language} K: K := \{ w \in \{0, 1\}^* \mid w\#w \in H \}$, where $H$ is the Halting Problem language defined as: $H := \{ w\#x \mid w, x \in \{0, 1\}^* \text{ and } M_w \text{ halts for the input } x \}$
  2. Arbitrary Language $B$: A language that is not further defined for this question.

The language in question, $A$, is the intersection of these two: $A := K \cap B$

My query pertains to the decidability status of $A$. I understand that if $B$ is undecidable, it doesn't necessarily imply that $A$ will also be undecidable, since the intersection of two undecidable languages can have different decidability properties.

Given this context, is the language $A$ decidable, semi-decidable, or undecidable? I'm looking for insights or theorems that could be applied to determine the decidability of $A$, considering the nature of $K$ and the potential characteristics of $B$.

  • 1
    $\begingroup$ The question is not clear. In the definition of $H$, what is $M_w$? Is $B$ arbitrary? What do you mean by "A language that is not further defined for this question"? If $B$ is the set of all words then $A = K$. If $B$ is empty, then $A = \emptyset$. The intersection can be anything, I don't see what you are trying to achieve. $\endgroup$ Commented Jan 6 at 15:07
  • $\begingroup$ Please edit your post to clarify what is the definition of $K$ and $B$. There seems to be some kind of typo in your definition of "Special Halting Problem", where words or symbols appear to be missing. Please proof-read and fix the mistakes. Please define $M_w$ and $H$. $\endgroup$
    – D.W.
    Commented Jan 6 at 21:59

1 Answer 1


There is no general answer.

$B$ could be decidable or undecidable, and $A$ could too, independently of $B$. This table contains different values of $B$ for all cases.

$B$ decidable $B$ undecidable
$A$ decidable ($A = \emptyset$) $B = \emptyset$ $B = H$
$A$ undecidable ($A = K$) $B = \{0, 1, \#\}^*$ $B = K$

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.