Show that the Collatz Conjecture would be provable if we could solve the halting problem This is problem 5.31 from Introduction to the Theory of Computation, 3rd Edition by Michael Sipser.

Let
  $$
f(x) =
\begin{cases}
3x+1, & \text{for odd $x$} \\
x/2,  & \text{for even $x$}
\end{cases}
$$
  for any natural number $x$. If you start with an integer $x$ and iterate $f$, you obtain a sequence, $x$, $f(x)$, $f(f(x))$, $\dots$ . Stop if you ever hit 1.
  For example, if $x = 17$, you get the sequence 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Extensive computer tests have shown that every starting point between 1 and a large positive integer gives a sequence that ends in 1. But the question of whether all positive starting points end up at 1 is unsolved; it is called the $3x + 1$ problem.
Suppose that $A_{TM}$ = $\{\langle M,w\rangle$∣ $M$ is a Turing Machine and $M$ accepts $w\}$ (Acceptance Turing machine) were decidable by a Turing Machine $H$. Use $H$ to describe a Turing Machine that is guaranteed to state the answer to the $3x + 1$ problem.

 A: I suppose the question is: if we can solve the halting problem, can we figure out the answer to the $3x+1$ (Collatz) problem?
Well, if we have a program $H$ that solves the halting problem (that is, it can decide whther some Turing machine $M$ with input $I$ halts or not), then do the following:
Create a Turing machine $F$ that takes a number $x$ and iterates through the $f(x)$ sequence, and stops once it reaches $1$. It is easy to show such a Turing machine $F$ exists .. here is its pseudocode:
F (input $i$)
$Begin$
$\quad$ While $i \not = 1$
$\quad \quad $ Case $i$ is even: $i = i/2$
$\quad \quad $ Case $i$ is odd: $i = 3*i+1$
$End$
(So this F routine will halt whenever the sequence ends with a 1 ... otherwise it will go on forever)
Now create a new Turing machine $C$ that starts with a given $i$, and that calls halting program $H$ on $F$ and $i$. If $H$ says that $F$ does not halt on $i$, then stop. If $H$ says that $F$ does halt $i$, then increase $i$ by $1$, and repeat the process. Again, it is easy to show that such a Turing machine $C$ exists, assuming $H$ exists .. here is its pseudocode:
C (input $i$)
$Begin$
$\quad$ While $H(F,i)$ 
$\quad \quad$ $i=i+1$
$End$
(so this routine $C$ will only stop if for some $i$, $H$ finds that $F$ does not halt on $i$. Effectively, $C$ looks for a counterexample to the Collatz conjecture. If there is one, then $C$ will eventually run into it. If there isn't, then $C$ will run forever)
Finally, call $H$ on $C$ and $1$. If $H$ says that $C$ with $1$ will not halt, then apparently the solution to the $3x+1$ is that the sequence will always end up with $1$ for any $x$ (that is, there is no counterexample to the Collatz conjecture ... so the Collatz Conjecture is true). If $H$ says that $C$ with $1$ does halt, then apparently the solution is that for some $x$ the sequence does not end up with $1$ (i.e. there is a counterexample to the Collatz conjecture). So, either way, you have solved the $3x+1$ Collatz problem.
