Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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!

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.