2

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?

hmakholm left over Monica
  • 286,031
mathemage
  • 810
  • 1
  • 6
  • 14

1 Answers1

4

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.

hmakholm left over Monica
  • 286,031
  • 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 = $?
     – mathemage Nov 04 '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 04 '13 at 23:50