primitive recursive functional equivalence

Question

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many algorithms for sorting they all describe the same relation. Given two primitive recursive implementations of A, and B, can they be proven to represent the same function? Please note that this question is not about unrestricted recursion, and as such not limited by the properties of Turing machines.

I know that if you have two functions that halt, and have a finite domain they can be proven to be the same function because you can simply try every possible input, and compare the output of each function. My confusion is when working with things working on say natural numbers because they are not finite.

If this is not decidable for the primitive recursive functions is it possible for weaker classes like say the elementary recursive functions. I also know that this IS possible for weaker things like finite state machines, and deterministic pushdown automata. Thanks.

Answer 1

It is well known that equivalence is undecidable even for CFGs resp. PDAs (see even Wikipedia). This provides a proof that the same property is undecidable for every model of any superset of CFL (by a simple special case reduction).

Since solving the word problem for any given CFL is clearly primitive recursive (by virtue of your favorite parsing algorithm), this includes the set of primitive recursive functions/algorithms.

Answer 2

It is not decidable, by the relatively straightforward informal proof:

Given an arbitrary Turing machine $M$, you can define the following function $f_M$:

$$ f_M(n) = \cases{0 \mbox{ if $M$ does not halt in $\leq n$ steps on empty input}\\ 1\mbox{ otherwise}}$$

It's a fundamental fact of primitive recursion that $f_M$ is, in fact, primitive recursive (it "simulates" $M$ for $n$ steps).

Now the statement $$ M \mbox{ does not halt on empty input}$$

is equivalent to

$$ \forall n,\ f_M(n) = {\bf0}(n)$$ where $\bf 0$ is the function which always returns $0$. The language of functions which do not halt is undecidable, and so, the above equivalence of primitive recursive functions is undecidable for general $f_M$.

It's not too hard to show that deciding equivalence of primitive recursive functions is in fact in $\Pi^0_1$, that is to say exactly as hard as determining non-termination of Turing machines, or deciding arithmetic sentences with a single non-bounded universal quantifier (and possibly bounded $\forall$ and $\exists$).