How to prove Transitive property of Reducibility with a TM?

Problem Detail: 

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?

Asked By : Iancovici

Answered By : Luke Mathieson

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:

1. $x \in A \Leftrightarrow g(f(x)) \in C$.
2. $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} < b) \wedge (b <c) \Rightarrow (10^{100} < c)$ show that $(a < b) \wedge (b <c) \Rightarrow (a < c)$?)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11536