3 ms·

Anybody know why there doesn't exist a complete implementation? What makes the hardest portions so difficult to implement compared to the rest?

• userbinator 3y ago
  https://en.wikipedia.org/wiki/Risch_algorithm#Decidability https://en.wikipedia.org/wiki/Risch_algorithm#Decidability seems to be the most difficult part; and it is unusual in that the Wikipedia article itself doesn't seem to clearly link to the original description of the algorithm.
  • dataflow 3y ago
    The comments underneath the post explain that zero-testing isn't the issue: https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm#comment948140_374089 https://mathoverflow.net/questions/374089/does-there-exist-a...
  • xg15 3y ago
    Still a bit puzzled by it. It's no surprise that the algorithm is incomplete, if some of its subtasks are still open problems in math. (And therefore it has to resort to imperfect heuristics or try and detect classes of inputs for which no results can be generated) However, the OP and links sound as if even just implementing the existing algorithm spec is so insanely hard that no one has managed to do so yet for the entirety of it. It'd be interested to know what exactly makes it so hard. Wikipedia doesn't link to the actual spec unfortunately, though they do mention that the spec is something like 100 pages in size. Maybe that's a hint of the amount of complexity that is involved...