2
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Nov 4, 2013 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$ Commented Nov 4, 2013 at 23:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.