3 ms·
One solution to the problem of measuring the length of the Python program is to turn it into machine code and measure that instead: https://stackoverflow.com/q
by luc4sdreyer 8y ago
One solution to the problem of measuring the length of the Python program is to turn it into machine code and measure that instead:
https://stackoverflow.com/questions/138521/is-it-feasible-to-compile-python-to-machine-code https://stackoverflow.com/questions/138521/is-it-feasible-to...
- Y_Y 8y agoDoesn't this just kick the problem down the road? Now you've introduced the optimisation of the compiler abd the expressiveness of your processor's machine language. The problem of knowing you have the "best" solution remains. I think if you are trying to come up with a canonical languahe to measure kolmogorov complexity in you can do better, like Binary Lambda Calculus. https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
- ddxxdd 8y agoThe same mathematical problem or operation can have several different Kolmogorov complexities, depending on how efficient an algorithm is when solving the problem. I don't think there's any way around it. If I create a Turing Machine that calculates 1+1 by counting all the atoms in the universe, it's going to have a high complexity.
- empath75 8y agoThe compiler might optimize out the entire calculation because it won’t change at runtime.