5 ms·

Finding the optimal execution time of an arbitrary program is equivalent to the halting problem. [1] If you narrow the “arbitrary” constraint to only include we

by Denzel 6y ago

Finding the optimal execution time of an arbitrary program is equivalent to the halting problem. [1] If you narrow the “arbitrary” constraint to only include well-structured, analyzable, guaranteed-to-terminate programs, then you can at least start to approximate a solution. Finding the true optimal case, even under those conditions, would be computationally expensive. [1]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem

chmod775 6y ago
This wasn't about anything related to optimal execution time. That an optimizer needs to know whether the code it optimizes terminates (or how long it runs) would also need proof if you'd want to go that route. The assumptions and optimizations the optimizer is allowed to use and what kinds of programs we're talking about, and what even is considered an "optimal program" is also still unclear (Edit: I'm assuming lowest number of instructions executed serially?). Please do refer me to a paper. Please do not link me vaguely related Wikipedia articles.
- vidarh 6y ago
  It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. The parallel to the halting problem is that with access to the output of the optimiser, you can always construct a problem where whatever the optimiser produces can be obstructed by producing an input that makes the optimised program non-optimal for the given input. A trivial example of such a program is a function that sorts it input and returns the sorted result, as no sort is optimal for all inputs.
  - chmod775 6y ago
    > It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. If you define optimal as: "A solution is optimal only if for every possible input there exists no solution that requires a lower number of instructions.", then yes, there can be no optimal sorting algorithm. I would argue that in practice only the first definition is useful. Further, you're assuming that "optimizations" that replace an existing algorithm with an equivalent one are allowed. Which brings me back to one of my original questions: What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable.
    - vidarh 6y ago
      > You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. I did not prove no optimal solution can exist. I gave an example of a subset of programs which would resist optimal optimisation. For a lot of programs an optimal version will exist. E.g. "return false" is obviously trivial to generate an optimal version of. [I'll also note hvidgaard provided a far simpler proof this problem is equivalent to the halting problem that invokes the halting problem directly as part of the solution by forcing the optimiser itself to solve the halting problem to determine the valid resolution, but my example shows that the optimiser can not solve the general case even if the program being optimised is guaranteed to halt] > But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. The commenter you replied to gave a definition: "finding the fastest way a program can be executed". However, I believe your definition won't help (even if I ignore the "lowest average number of instructions" - nobody cares about the number of instructions executed, but at about wall-clock time or space complexity, or possibly the size of the generated code), because the input to the program and the input to the sorting routine here are not necessarily the same. You can extend the sort problem to a more complex program that can incorporate the element that reads back in its own binary and perturbs the inputs fed to the sort component. Indeed to "borrow" from hvidgaard, you have no guarantee that the program in totality will halt at all, but even if you disregard not halting, as long as the program can read its own code, the problem remains. > I would argue that in practice only the first definition is useful. In practice that definition is very often totally useless, because we very often have knowledge about the expected input data for which the way we express an algorithm and the specific choice of algorithm is the only way most programming languages allow us to express the necessary expectations. Effectively most optimisers aren't advanced enough anyway that this is a consideration, because we're hitting space-time complexity tradeoffs for the cost of running the optimisers already when trying to do unambiguously beneficial optimisations. > What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable. Given the claim was stated without any constraints, it is natural to assume the claim was general. That is, that a valid output of the optimiser is a program that given the same input produces the same output. The point of the claim was to point out the sheer complexity of aiming for auto-parallelisation beyond smaller transformations.

by Denzel 6y ago

chmod775 6y ago

This wasn't about anything related to optimal execution time. That an optimizer needs to know whether the code it optimizes terminates (or how long it runs) would also need proof if you'd want to go that route. The assumptions and optimizations the optimizer is allowed to use and what kinds of programs we're talking about, and what even is considered an "optimal program" is also still unclear (Edit: I'm assuming lowest number of instructions executed serially?). Please do refer me to a paper. Please do not link me vaguely related Wikipedia articles.

vidarh 6y ago
It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. The parallel to the halting problem is that with access to the output of the optimiser, you can always construct a problem where whatever the optimiser produces can be obstructed by producing an input that makes the optimised program non-optimal for the given input. A trivial example of such a program is a function that sorts it input and returns the sorted result, as no sort is optimal for all inputs.
- chmod775 6y ago
  > It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. If you define optimal as: "A solution is optimal only if for every possible input there exists no solution that requires a lower number of instructions.", then yes, there can be no optimal sorting algorithm. I would argue that in practice only the first definition is useful. Further, you're assuming that "optimizations" that replace an existing algorithm with an equivalent one are allowed. Which brings me back to one of my original questions: What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable.
  - vidarh 6y ago
    > You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. I did not prove no optimal solution can exist. I gave an example of a subset of programs which would resist optimal optimisation. For a lot of programs an optimal version will exist. E.g. "return false" is obviously trivial to generate an optimal version of. [I'll also note hvidgaard provided a far simpler proof this problem is equivalent to the halting problem that invokes the halting problem directly as part of the solution by forcing the optimiser itself to solve the halting problem to determine the valid resolution, but my example shows that the optimiser can not solve the general case even if the program being optimised is guaranteed to halt] > But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. The commenter you replied to gave a definition: "finding the fastest way a program can be executed". However, I believe your definition won't help (even if I ignore the "lowest average number of instructions" - nobody cares about the number of instructions executed, but at about wall-clock time or space complexity, or possibly the size of the generated code), because the input to the program and the input to the sorting routine here are not necessarily the same. You can extend the sort problem to a more complex program that can incorporate the element that reads back in its own binary and perturbs the inputs fed to the sort component. Indeed to "borrow" from hvidgaard, you have no guarantee that the program in totality will halt at all, but even if you disregard not halting, as long as the program can read its own code, the problem remains. > I would argue that in practice only the first definition is useful. In practice that definition is very often totally useless, because we very often have knowledge about the expected input data for which the way we express an algorithm and the specific choice of algorithm is the only way most programming languages allow us to express the necessary expectations. Effectively most optimisers aren't advanced enough anyway that this is a consideration, because we're hitting space-time complexity tradeoffs for the cost of running the optimisers already when trying to do unambiguously beneficial optimisations. > What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable. Given the claim was stated without any constraints, it is natural to assume the claim was general. That is, that a valid output of the optimiser is a program that given the same input produces the same output. The point of the claim was to point out the sheer complexity of aiming for auto-parallelisation beyond smaller transformations.