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).)

Hmm. If we’re trying to argmax some function f over the real numbers, then the simplest algorithm would be something like “iterate over all mathematical expressions e; for each one, check whether the program ‘iterate over all provable theorems, halting when you find one that says e=argmaxf’ halts; if it does, return e.”

...but I guess that’s not guaranteed to ever halt, since there could conceivably be an infinite procession of ever-more-complex expressions, eking out ever-smaller gains on f. It seems

possiblethat no matter what (reasonably powerful) mathematical language you choose, there are function-expressions with finite maxima at values not expressible in your language. Which is maybe what you meant by “as far as I know there can’t be [an algorithm for it].”(I’m assuming our mathematical language doesn’t have the word argmax, since in that case we’d pretty quickly stumble on the expression argmaxf, verify that argmaxf=argmaxf, and return it, which is obviously a cop-out.)