World's most popular travel blog for travel bloggers.

[Answers] primitive recursive functional equivalence

, , No Comments
Problem Detail: 

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.

Asked By : Harpo Roeder

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback