Am 19.01.2015 um 22:28 schrieb Amit Saha:
I'm assuming that SymPy does not even attempt to identify unsolvable
problems. If that is indeed true, "unsolvable" is a proper subset of "not
implemented", at least from SymPy's perspective, and SymPy does not
distinguish between the two.
I am not sure if I would say "unsolveable" is a proper subset of "not
implemented".
It is. Determining the set of unsolveable problems is itself an
unsolveable problem.
Full disclosure: It is logically impossible to write an algorithm that
can take arbitrary problem descriptions of whatever formalism you
choose, and always determine whether that problem is solvable.
Any correct algorithm will run into an endless loop for an at least
countably infinite subset of the set of possible problems.
And there is no algorithm for determining that subset (that would allow
constructing an algorithm that would work for all cases, which is a
contradiction for the result that there's no such algorithm).
Proof essentially based on Goedel's incompleteness theorem, so this
applies to all logic systems and algorithms that can handle countable
infinities.
(Computer scientists call this the "halting problem".)
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/54BD7CD5.209%40durchholz.org.
For more options, visit https://groups.google.com/d/optout.
