6 ms·

> 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 e

> 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.
- chmod775 6y ago
  I do not understand why you are trying to drag the discussion from mathematically provable statements into whatever territory this is. In any case your response is not very readable - some sentences are cut off halfway through or mangled. Maybe you could fix it up and I'll give it a second reading afterwards. > Given the claim was stated without any constraints The original commenter was suggesting there is some mathematical proof for the statement: "finding the fastest way a program can be executed is known uncomputable." Given the context it would seem likely that the optimizations they were talking about are specifically about finding which instructions can be executed in parallel. Consider their next sentence: "The best we can do is identify _some_ concurrency optimizations." We won't be getting anywhere like this either way. This started with me asking for clarification and a reference, and you keep trying to present me with something that is neither. I can appreciate you wanting to add some insights, but only hvidgaard itself would know what they meant to say. Edit: They posted a response 3 hours ago which I did not see until now. That settles that.
  - vidarh 6y ago
    I've fixed the incomplete statement, but it does not make a material change. If you don't understand the argument, I'm not sure how to restate it to make it clearer. > The original commenter was suggesting there is some mathematical proof for the statement: "We know that an optimal optimization, i.e. finding the fastest way a program can be executed is known uncomputable." And they have provided a proof for that, which was short and concise. > Given the context it would seem likely that the optimizations they were talking about are specifically about finding which instructions can be executed in parallel. I'd rather - given that it matches their followup proof - assume that the statement is intended to be taken as written rather than assuming additional constraints that they did not state anywhere. > Consider their next sentence: "The best we can do is identify _some_ concurrency optimizations." Yes, because we can not create an optimal program. This is not attaching any limitations to the hypothetical optimiser from the previous statement. > This started with me asking for clarification and a reference, and you keep trying to present me with something that is neither. I stated a proof by giving an example that can not be optimally optimised according to the criteria hvidgaard stated. I'm sorry if it wasn't clear enough for you. It was more complicated than hvidgaards very elegant proof, granted, though it also goes further, in showing that even for programs that do terminate there exists a subset which there is no solution that meets hvidgaards criteria. > I can appreciate you wanting to add some insights, but only hvidgaard itself would know what they meant to say. hvidgaard has also stated a proof, by showing that you can devise a program that requires the optimiser to solve the halting problem to return the optimal program, that just like mine made no assumptions about the set of allowed optimisations. I don't know what you're still arguing here given that whatever you think of my sort example, hvidgaards own proof for their statement is simple an unambiguous. This is also not at all a new discovery either, but a well settled topic of computer science.

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.

chmod775 6y ago
I do not understand why you are trying to drag the discussion from mathematically provable statements into whatever territory this is. In any case your response is not very readable - some sentences are cut off halfway through or mangled. Maybe you could fix it up and I'll give it a second reading afterwards. > Given the claim was stated without any constraints The original commenter was suggesting there is some mathematical proof for the statement: "finding the fastest way a program can be executed is known uncomputable." Given the context it would seem likely that the optimizations they were talking about are specifically about finding which instructions can be executed in parallel. Consider their next sentence: "The best we can do is identify _some_ concurrency optimizations." We won't be getting anywhere like this either way. This started with me asking for clarification and a reference, and you keep trying to present me with something that is neither. I can appreciate you wanting to add some insights, but only hvidgaard itself would know what they meant to say. Edit: They posted a response 3 hours ago which I did not see until now. That settles that.
- vidarh 6y ago
  I've fixed the incomplete statement, but it does not make a material change. If you don't understand the argument, I'm not sure how to restate it to make it clearer. > The original commenter was suggesting there is some mathematical proof for the statement: "We know that an optimal optimization, i.e. finding the fastest way a program can be executed is known uncomputable." And they have provided a proof for that, which was short and concise. > Given the context it would seem likely that the optimizations they were talking about are specifically about finding which instructions can be executed in parallel. I'd rather - given that it matches their followup proof - assume that the statement is intended to be taken as written rather than assuming additional constraints that they did not state anywhere. > Consider their next sentence: "The best we can do is identify _some_ concurrency optimizations." Yes, because we can not create an optimal program. This is not attaching any limitations to the hypothetical optimiser from the previous statement. > This started with me asking for clarification and a reference, and you keep trying to present me with something that is neither. I stated a proof by giving an example that can not be optimally optimised according to the criteria hvidgaard stated. I'm sorry if it wasn't clear enough for you. It was more complicated than hvidgaards very elegant proof, granted, though it also goes further, in showing that even for programs that do terminate there exists a subset which there is no solution that meets hvidgaards criteria. > I can appreciate you wanting to add some insights, but only hvidgaard itself would know what they meant to say. hvidgaard has also stated a proof, by showing that you can devise a program that requires the optimiser to solve the halting problem to return the optimal program, that just like mine made no assumptions about the set of allowed optimisations. I don't know what you're still arguing here given that whatever you think of my sort example, hvidgaards own proof for their statement is simple an unambiguous. This is also not at all a new discovery either, but a well settled topic of computer science.