Primitive recursive functions can simulate every single step of a Turing machine. In order to prove this, one has to see that a function defined by state table is primitive recursive.

Simply speaking, a partial function $f\colon \mathbb{N} \to \mathbb{N}$ with finite domain is always primitive recursive. That is, if-else and switch-case constructs (in programming languages) can be represented by appropriate primitive recursive functions. How to prove this property?


You can directly write down a definition of the conditional function by primitive recursion:

$$ f(c,x,y) = \begin{cases} y & \text{if }c=0 \\ x & \text{if }c\ge 1 \end{cases} $$

This may not look primitive recursive, but nobody says the recursive case actually has to use the value of $f(c-1,x,y)$.

If you want a switch with more than two cases, just chain a number of if-then-elses together.

| cite | improve this answer | |
  • $\begingroup$ Oh, this is pretty elegent! 1. So do you mean that $f(c,x,y) = P_3^4(c-1, f(c-1,x,y), x, y) = x$, that is, the iteration of the recursion is just projection to third argument? 2. How do you go around when you want condition different from $c = 0$, say, $c = 42$ or $c = <other hardcoded constant>$? $\endgroup$ – mathemage Nov 4 '13 at 21:35
  • $\begingroup$ @mathemage: Yes, that's what I mean. For another comparison you first need to implement a function that returns $0$ exactly when its argument is $42$, e.g. as $h(x)=(x\dot-42)+(42\dot-x)$. $\endgroup$ – hmakholm left over Monica Nov 4 '13 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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