On Thu, Nov 20, 2014 at 7:53 PM, Bill Page <bill.p...@newsynthesis.org> wrote: > 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.
I see. But what does this have to do with the derivative of |f(x)| that we are trying to figure out? As you pointed out, the challenge is that if you include conjugate(x), then you might be out of luck. But aren't you out of luck already if you have abs(x) in the expression in the first place? I.e. taking a derivative is not going to change anything, you are still out of luck. > >> 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). I see, clever. > >> >> 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. Sure, this might be one of the many methods in a CAS. Ondrej -- 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.
