3 ms·
One of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program
by zbobet2012 3y ago
One of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program that generates that string. Which fundamentally is the question of compression. So these undecidable problems actually have a lot of practical value.
https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
- nl 3y agoAnd Kolmogorov complexity is used by Shane Legg (DeepMind founder) and Marcus Hutter (Hutter prize etc) in their paper "A Formal Measure of Machine Intelligence" http://www.vetta.org/documents/legg-hutter-2006-formal-measure-intelligence.pdf http://www.vetta.org/documents/legg-hutter-2006-formal-measu...