4 ms·

There is no general algorithm to symbolically compute all integrals. All we have are partial algorithms which consist of big rulebooks for the cases we’ve alrea

There is no general algorithm to symbolically compute all integrals. All we have are partial algorithms which consist of big rulebooks for the cases we’ve already solved. It also turns out we can’t even verify, in general, the result of integration: Suppose you are given two functions, f(x) and G(x), and are told that G(x) is an antiderivative of f(x). So then you let g(x) = G’(x), the derivative of G(x). Now if G(x) is truly an antiderivative of f(x) then we must have g(x) = f(x) but unfortunately the problem of determining whether two functions are equal is undecidable (a consequence of the halting problem).

carbotaniuman 2y ago
Does the functional equality being impossible to determine thing work for math problems? I know it works for computable functions, but math functions are pure and total so it seems easier.
- chongli 2y ago
  Math functions are not total, in general. Computable functions are a subclass of all functions, so lots of functions are not computable. Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
- kccqzy 2y ago
  Just determining the equality of two real numbers is difficult.
- xigoi 2y ago
  The problem is that what you’re comparing are not functions, but representations of functions.
Someone 2y ago
> There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html) ‘only’ handles “rational functions, radicals, logarithms, and exponential functions”, but may never have been fully implemented (https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)

carbotaniuman 2y ago

Does the functional equality being impossible to determine thing work for math problems? I know it works for computable functions, but math functions are pure and total so it seems easier.

chongli 2y ago
Math functions are not total, in general. Computable functions are a subclass of all functions, so lots of functions are not computable. Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
kccqzy 2y ago
Just determining the equality of two real numbers is difficult.
xigoi 2y ago
The problem is that what you’re comparing are not functions, but representations of functions.

Someone 2y ago

> There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html) ‘only’ handles “rational functions, radicals, logarithms, and exponential functions”, but may never have been fully implemented (https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)