# $\mu$-recursive definition of ulam (3n+1) function

$\newcommand{\ulam}{\operatorname{ulam}}$

The ulam function is defined as $$\ulam(x) = \begin{cases} 1 & x = 1 \\ \ulam\left( \frac{x}{2}\right) & x \text{ even}\\ \ulam(3x+1) & x\text{ odd}\end{cases}$$

I want to show that $\ulam$ is $\mu$-recursive by using primitive recursive functions and the $\mu$ opterator - not by e.g. defining a Turing machine.

This is a solution I got - but I don't understand it completely and it might above all be wrong.

$$\begin{eqnarray*} f_p(x) & := & \begin{cases}\frac{x}{2} & x \text{ even} \\ 3x + 1 & x \text{ odd} \end{cases} \\ f_b(x) & := & \begin{cases}0 & x = 1 \\1 & x \neq 1\end{cases} \\ g(0,x) &=& x \\ g(n+1,x) &=& f_p(g(n,x)) \\ h(n,x) &=& f_b(g(n,x)) \\ \ulam(x) &=& g(\mu(h)(x),x) \end{eqnarray*}$$

I do understand what the $\mu$ operator does in common, but there's still a gap in my mind between "find the smallest argument that returns zero" and a concrete application such "ulam".

Could you please check the solution and try to explain it to me?

$$\newcommand{\ulam}{\operatorname{ulam}}$$To compute $$\ulam(x)$$ using the original definition, you compute a bunch of other values of $$\ulam$$ until you reach $$\ulam(1)$$ and then you return $$1$$. For example, \begin{aligned} \ulam(3) &= \ulam(10) \\&= \ulam(5) \\&= \ulam(16) \\&= \ulam(8) \\&= \ulam(4) \\&= \ulam(2) \\&= \ulam(1) = 1.\end{aligned} Since the 3n+1 Conjecture is still open, we don't know whether this process always ends and thus $$ulam$$ is the constant function with value $$1$$ or if the sequence of computations sometimes goes on forever and never gives an answer.
The alternative definition you give proceeds as follows. The primitive recursive function $$g(n,x)$$ gives the $$n$$th input to $$\ulam$$ in the above computation, where the $$0$$th input is $$x$$. For example, $$g(0,3) = 3$$ and then \begin{aligned} g(1,3) &= f_p(3) = 10, \\g(2,3) &= f_p(10) = 5, \\g(3,3) &= f_p(5) = 16, \\ g(4,3) &= f_p(16) = 8, \\ g(5,3) &= f_p(8) = 4, \\g(6,3) &= f_p(4) = 2, \\ g(7,3) &= f_p(2) = 1,\end{aligned} and then the values keep repeating $$4,2,1$$ ad infinitum.
To compute $$\ulam(x)$$ you need to stop as soon as you reach $$1$$ and then return the value $$1$$. By definition of $$f_b$$, $$h(n,x) = 0$$ if $$g(n,x) = 1$$ and $$h(n,x) = 1$$ in all other cases. Therefore, $$(\mu h)(x)$$ is the first number $$n$$ such that $$g(n,x) = 1$$, and $$(\mu h)(x)$$ is undefined if there is no such $$n$$. So, if $$(\mu h)(x)$$ is defined then $$\ulam(x) = 1$$ because the computation for $$\ulam(x)$$ stops after $$(\mu h)(x)$$ steps and returns $$1$$, and if $$(\mu h)(x)$$ is undefined then the computation for $$\ulam(x)$$ never stops and $$\ulam(x)$$ is therefore undefined. In either case, the computation for $$g((\mu h)(x),x)$$ has the same outcome as that for $$\ulam(x)$$.