How to prove Transitive property of Reducibility with a TM? How can we prove that $h(x) = g(f(x))$ is a reduction function for $A \leq_m C$,

if $f$ is the reduction function of  $A \leq_m B$ and $g$ is the reduction function for  $B \leq_m C$

The given Proposition is: $A \leq_m B, B \leq_m C \Rightarrow A \leq_m C$

I was thinking about using $HALT_{TM}$ for A. So on input $\langle M, w\rangle \in A$ if and only if $\langle M'',w'' \rangle \in  C$

The output of A would be $ \langle M', w' \rangle$ and the output of B would be $\langle M'',w'' \rangle$

If the constructed $M$ rejects the input $x$, then it loops forever, so $C$ is not recursive if $A$ is not recursive

If this isn't sufficient, then what am I missing?
The properties that reductions have are:


They preserve language membership (or Yes-instances, or whichever phrasing you prefer).
They are computable.


So then given that you have two reductions $f$, which takes instances of $A$ and produces instances of $B$ such that $x \in A \Leftrightarrow f(x) \in B$, and $g$ which does the same for $B$ and $C$, you need to show:


$x \in A \Leftrightarrow g(f(x)) \in C$.
$f\cdot g$ is computable.


The first should be a fairly straightforward application of basic logic. The second is also easy.

You can't just take $A=HALT_{TM}$ though, as all you would show then is that $HALT_{TM} \leq_{m} C$, whereas your question (appears) to ask for a proof of the transitivity of many-one reductions in general. (As a comparison would showing that $(10^{100} &lt; b) \wedge (b &lt;c) \Rightarrow (10^{100} &lt; c)$ show that $(a &lt; b) \wedge (b &lt;c) \Rightarrow (a &lt; c)$?)