On 20 November 2014 12:56, Ondřej Čertík <ondrej.cer...@gmail.com> wrote: > ... > Can you give an example of an expression that cannot be decided by > the Richardson's theorem?
Well, no not exactly. Richardson's theorem is not about individual expressions, it is about decidability, i.e. computability, in general. Consider an expression of the form f(x) - | f(x) | where f(x) is composed from integers, the variable x, +, * and sin. The question that Richardson's theorem answers is whether or not there exists a program that can determine if f(x) - |f(x)| = 0 for all x. This problem can be reduced to finding an algorithm to determine if f(x) is everywhere non-negative. Richardson proves that no such algorithm exists. > How does FriCAS do the zero testing? I.e. if you > give it > > f(x) = sin(x)^2 + cos(x)^2-1 > > how does it decide that it is equal to 0? This can be done by the function 'normalize' which first uses 'realElementary' to rewrite the expression using just 4 fundamental real-valued elementary transcendental functions (kernels): log, exp, tan, and arctan. E.g. sin(x) = 2*tan(x/2)/(tan(x/2)^2+1) cos(x) = (1-tan(x/2)^2)/(1+tan(x/2)^2) For your example this suffices but if necessary it next rewrites the result again using the minimum number of algebraically independent kernels. There is also a complex-valued version called 'complexElementary' which uses only log and exp but may introduce the constant sqrt(-1). > > Are we talking about functions of just one variable (f(x)) or more > (f(x, y, z, ...))? In general more than one variable. > > Why cannot you just use the probabilistic testing, where you plug in > various (complex) numbers into f(x) and test that it is equal to zero, > numerically. > I suppose that might be pragmatic but I would not call it "computer algebra" in the mathematical sense. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
