# Is definition by cases a primitive recursive function?

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?

$$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)$.
• 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>$? – mathemage Nov 4 '13 at 21:35
• @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)$. – hmakholm left over Monica Nov 4 '13 at 23:50