On Jun 25, 2012, at 6:26 AM, Alan Bromborsky <[email protected]> wrote:
> Subject for discussion - > > What parts of sympy are deterministic and what parts are non-deterministic > (I would think simplification and integration are in principal > non-deteriminstic) > > Should using an expert system such as pyclips be considered to improve the > non-deterministic parts of sympy? I'm assuming that by "deterministic" you mean "algorithmic", i.e., you can say something about what the computer can and cannot do, even for a broad class of inputs. Any given implementation may be deterministic or non-deterministic, depending on how it is implemented (e.g., if it contains random or semi-random elements like iteration through a dictionary, it will be non-deterministic). Deterministic just means that for the same input you will get the same output. Simplification is definitely non-algorithmic. For a class of expressions that is actually somewhat small (compared to what SymPy is capable of representing) it is undecidable, by Richardson's theorem. I think an expert system might actually be an interesting way to approach this problems, because there are definitely "rules of thumb" that humans apply when simplifying expressions, which are difficult to quantify. Other AI approaches might be tried too, like genetic algorithms. Integration is actually completely algorithmic for elementary functions, but requires heuristics if you expand beyond that. Some of the "heuristics" an be quite mathematically intense, though, so I don't know how applicable an expert system would be. For example, the heurisch algorithm implemented in SymPy works by taking a trial solution using knowledge of what an elementary antiderivative could look like, and solving for the coefficients to see if it works. If it doesn't work, it means that the degree of the trial expression needs to be increased, unless the expression has no elementary antiderivative, in which case no degree will be big enough. A degree bound is computable (and indeed this is what the bulk of the full Risch algorithm ends up doing), but it's not easy to guess just by looking at an expression. Actually, for most expressions you can guess correct, which is why the default for heurisch works for most expressions, but it's the corner cases that are tricky. Other heuristics are very simple, like table lookups. The only place I see an expert system being helpful there is in the actual pattern matching (which is a much more general problem). Aaron Meurer -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
