...When we can state code that would solve the problem given a hypercomputer, we have become less confused. Once we have the unbounded solution we understand, in some basic sense, the kind of work we are trying to perform, and then we can try to figure out how to do it efficiently.
ASHLEY: Which may well require new insights into the structure of the problem, or even a conceptual revolution in how we imagine the work we’re trying to do.
I’m not convinced your chess example, where the practical solution resembles the hypercomputer one, is representative. One way to sort a list using a hypercomputer is to try every possible permutation of the list until we discover one which is sorted. I tend to see Solomonoff induction as being cartoonishly wasteful in a similar way.
The understanding I came away with: there are (at least) three stages of understanding a problem:
You can’t write a program to solve it.
You can write a cartoonishly wasteful program to solve it.
You can write a computationally feasible program to solve it.
“Shuffle-sort” achieves the second level of knowledge re: sorting lists. Yeah, it’s cartoonishly wasteful, and it doesn’t even resemble any computationally feasible sorting algorithm (that I’m aware of) -- but, y’know, viewed through this lens, it’s still a huge step up from not even understanding “sorting” well enough to sort a list at all.
(Hmm, only marginally related but entertaining: if you reframe the problem of epistemology not as sequence prediction, but as “deduce what program is running your environment,” then a Solomonoff inductor can be pretty fairly described as “consider every possible object of type EnvironmentProgram; update its probability based on the sensory input; return the posterior PDF over EnvironmentProgram-space.” The equivalent program for list-sorting is “consider every possible object of type List<Int>; check if (a) it’s sorted, and (b) it matches the element-counts of the input-list; if so, return it.” Which is even more cartoonishly wasteful than shuffle-sort. Ooh, and if you want to generalize to cases where the list-elements are real numbers, I think you get/have to include something that looks a lot like Solomonoff induction, forcing countability on the the reals by iterating over all possible programs that evaluate to real numbers (and hoping to God that whatever process generated the input list, your mathematical-expression-language is powerful enough to describe all the elements).)
I’m not convinced your chess example, where the practical solution resembles the hypercomputer one, is representative. One way to sort a list using a hypercomputer is to try every possible permutation of the list until we discover one which is sorted. I tend to see Solomonoff induction as being cartoonishly wasteful in a similar way.
The understanding I came away with: there are (at least) three stages of understanding a problem:
You can’t write a program to solve it.
You can write a cartoonishly wasteful program to solve it.
You can write a computationally feasible program to solve it.
“Shuffle-sort” achieves the second level of knowledge re: sorting lists. Yeah, it’s cartoonishly wasteful, and it doesn’t even resemble any computationally feasible sorting algorithm (that I’m aware of) -- but, y’know, viewed through this lens, it’s still a huge step up from not even understanding “sorting” well enough to sort a list at all.
(Hmm, only marginally related but entertaining: if you reframe the problem of epistemology not as sequence prediction, but as “deduce what program is running your environment,” then a Solomonoff inductor can be pretty fairly described as “consider every possible object of type EnvironmentProgram; update its probability based on the sensory input; return the posterior PDF over EnvironmentProgram-space.” The equivalent program for list-sorting is “consider every possible object of type List<Int>; check if (a) it’s sorted, and (b) it matches the element-counts of the input-list; if so, return it.” Which is even more cartoonishly wasteful than shuffle-sort. Ooh, and if you want to generalize to cases where the list-elements are real numbers, I think you get/have to include something that looks a lot like Solomonoff induction, forcing countability on the the reals by iterating over all possible programs that evaluate to real numbers (and hoping to God that whatever process generated the input list, your mathematical-expression-language is powerful enough to describe all the elements).)