Is the function $h$ defined by measuring the number of steps the Collatz conjecture partial recursive?

75 Views Asked by At

Is the function $h$ defined by measuring the number of steps the Collatz conjecture takes to reach $1$ or undefined if it never reaches $1$ partial recursive?

I believe so since the function of the Collatz conjecture seems to be primitive recursive (unsure how to prove this as I can't define $f(n+1)$ from $f(n)$ but $ 3n + 1 = succ(m(3,n))$ where $succ$ and $m$ are successor and multiplication and $n/2 = m : m(2,m) = n$), but I'm not sure how the undefined part of $h$ works.

1

There are 1 best solutions below

0
On

The Collatz function, $C(n)=3n+1$ for odd $n$ and $n/2$ for even $n$, is primitive recursive. Therefore so is its iteration $C^k(n)$, defined by the primitive recursion $C^0(n)=n$ and $C^{k+1}(n)=C(C^k(n))$. Finally, your $h$ can be defined by minimization as $h(n)=\mu k.(C^k(n)=1)$, and so $h$ is partial recursive.