I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on.

Let us call 2 Turing machines related if there is an input $w$ on which both halt (after finitely many steps). Let $h(M )$ be the set of inputs on which the TM $M$ halts.

Show that the problem $\text{RELATED} = \{\langle M1, M2\rangle \mid h(M1) \cap h(M2) \neq \emptyset\}$ is Turing recognizable.

Assume, you know that the halting problem $H$ is undecidable. Show that the problem $\text{RELATED}$ is undecidable. Show this result by defining an appropriate mapping reduction $g$.


1 Answer 1


To show $\mbox{RELATED} \in \mathsf{RE}$, you can enumerate all pairs $\langle w,t \rangle \in \Sigma^* \times \mathbb{Z}^+$ in dovetail fashion. For each pair check whether both $M_1$ and $M_2$ halt on $w$ within $t$ steps.

Given $x \in \Sigma^*$, you can compute a description of a Turing machine $M_x$ that halts if and only if its input is $x$. Since $\langle T, x \rangle \in H \iff \langle T, M_x\rangle \in \mbox{RELATED}$, we must have $\mbox{RELATED} \not\in \mathsf{R}$.


Your Answer

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

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