Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two functions in closed form such that f(x) is the same for all x for both functions, is there always a way to manipulate either function to make it so they are written exactly the same or can you have two functions that can be proven equivalent yet neither can be simplified to look the same as the other?

share|improve this question
2  
Here is a paper you might be interested in seeing. –  J. M. Aug 4 '12 at 16:51

2 Answers 2

up vote 2 down vote accepted

Your question is equivalent to asking if there is some normal form for every closed form expression that we can reduce equivalent expressions to.

Now the answer depends on the kind of formal system you use, i.e. what exactly you call closed form. Surely when we're restricting ourselves to few enough operations, there is. Take e.g. arithmetic terms containing natural numbers, +, $\cdot$ and variables, we can completely simplify the terms, thus yielding a normal form.

However for some not too complicated systems like λ-calculus, which just consists of function creation and application, is has been proven that deciding whether two terms are equivalent is already undecidable, so there is no normal form.

share|improve this answer
    
Is there a standard method to prove that a given function has no normal form or does the method very with the system? –  Jesse Stern Aug 4 '12 at 16:48
1  
I don't know such a method, but I know little in this field anyway so there might be. However, reasoning about formal systems can easily get veery complex, so I doubt there is. –  Dario Aug 4 '12 at 17:42

For an explicit description of a situation where the identity problem is recursively unsolvable, see Richardson's Theorem.

Here the allowed operations are the constant function $\log 2$, the ordinary operations of arithmetic, $\exp$, $\sin$, absolute value, and composition of functions. There is no algorithm to determine whether an expression $f(x)$ built up using the single variable $x$ and the allowed operations is identically equal to $0$ on the reals.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.