Turing recognizability and Reduction Mapping on pairs of related Turing machines

Question

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$.

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}$.