"Kolmogorov complexity is somewhat different from proof complexity, but it's also not computable. A brute-force program that outputs the shortest proof of an input sentence is easy to write, but it will necessarily run forever on certain inputs; there's no computable way to know when to stop searching."
"The Kolmogorov complexity is an uncomputable size. So we won't be able to find the lowest complexity in general, no matter how powerful our theory is."
Get involved in philosophical discussions about knowledge, truth, language, consciousness, science, politics, religion, logic and mathematics, art, history, and lots more. No ads, no clutter, and very little agreement — just fascinating conversations.