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.