3 ms·

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 respons

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.
- chmod775 6y ago
  I did not see hvidgaards' response until now. It's fairly recent (3h) and way up the thread. And yes, I'm well aware that the issue is settled for general optimizations. At risk of repeating myself for a third time: I was curious whether, when only using optimizations that involve re-ordering instructions/finding instructions that can be executed in parallel, there is proof that there exists no optimal solution. If that's still not clear, I'll quote myself from my original comment: > Was the assumption that you'd also be (infinitely) unrolling loops or maybe 'rewriting' the program into something equivalent but faster? What does "finding the fastest way a program can be executed" mean? Just re-ordering instructions and distributing them across threads, or something more? Quite disappointingly that wasn't what they were speaking of, because I would've been quite surprised by such a proof for reasons outlined in my original comment.
  - hvidgaard 6y ago
    There always exists _an_ optimal solution for any given algorithm. But question is if you can compute such an optimal solution. Or even if you can compute if a solution is optimal. I would say that a reasonable definition of an optimal solution to a problem, excluding concurrency for now, is the same as minimizing the number of steps needed to complete the algorithm. Take my proof from the other comment, it states that if you have a perfect optimizer, you have solved the halting problem. Adding concurrency to the optimization, i.e. the OPT function can return a program that executes concurrently in which ever way possible on some given hardware. It will still return "return false;" if and only if the original algorithm never terminates.
    - chmod775 6y ago
      Yes. I should've said "proof that the optimal solution is uncomputable". My bad.
      - hvidgaard 6y ago
        Then I do not understand what you're asking. My proof is just that. If you have a non terminating TM and a program simulating it after i steps and return true only if it's in an accepting state, the optimal solution to that would always be "return false" for TMs that do not ever terminate, which is solving the halting problem. This goes for any optimization you can think of.

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.

chmod775 6y ago
I did not see hvidgaards' response until now. It's fairly recent (3h) and way up the thread. And yes, I'm well aware that the issue is settled for general optimizations. At risk of repeating myself for a third time: I was curious whether, when only using optimizations that involve re-ordering instructions/finding instructions that can be executed in parallel, there is proof that there exists no optimal solution. If that's still not clear, I'll quote myself from my original comment: > Was the assumption that you'd also be (infinitely) unrolling loops or maybe 'rewriting' the program into something equivalent but faster? What does "finding the fastest way a program can be executed" mean? Just re-ordering instructions and distributing them across threads, or something more? Quite disappointingly that wasn't what they were speaking of, because I would've been quite surprised by such a proof for reasons outlined in my original comment.
- hvidgaard 6y ago
  There always exists _an_ optimal solution for any given algorithm. But question is if you can compute such an optimal solution. Or even if you can compute if a solution is optimal. I would say that a reasonable definition of an optimal solution to a problem, excluding concurrency for now, is the same as minimizing the number of steps needed to complete the algorithm. Take my proof from the other comment, it states that if you have a perfect optimizer, you have solved the halting problem. Adding concurrency to the optimization, i.e. the OPT function can return a program that executes concurrently in which ever way possible on some given hardware. It will still return "return false;" if and only if the original algorithm never terminates.
  - chmod775 6y ago
    Yes. I should've said "proof that the optimal solution is uncomputable". My bad.
    - hvidgaard 6y ago
      Then I do not understand what you're asking. My proof is just that. If you have a non terminating TM and a program simulating it after i steps and return true only if it's in an accepting state, the optimal solution to that would always be "return false" for TMs that do not ever terminate, which is solving the halting problem. This goes for any optimization you can think of.