= 27d567bc2d48d9f40e9ccc20ea370b15)
nshepperd comments on Complexity and Intelligence - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (75)
If you could compute them, you could use that computation (in a complicated way) to produce strings that could only be produced by much longer programs. This is a contradiction, so it's not possible to compute complexity.
And I guess you can't just enumerate all programs and take the length of the shortest (=first) one that produces the string because of the halting problem?
I wonder if I could turn that around and spin a computation of complexity into a halting oracle...