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?

Thanks in advance!


1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .