I made it clear what I mean:

Search that is possibly guided by experience solving similar problems. By learning from past experiences, search becomes more efficient.

I agree that there's a lot more work to be done in AI. We need to find better learning and search algorithms.

Why did I mention this at all? Because there's no other way to do this. Creativity (coming up with new unprecedented solutions to problems) must utilize some form of search, and due to the no-free-lunch theorem, there is no shortcut to finding the solution to a problem. The only thing that can get around no-free-lunch is to consider an ensemble of problems. That is, to learn from past experiences.

And about your point:

It is not obvious to me that Deutsch is familiar with ideas like Solomonoff induction, Pearl's work on causality, and so on, and thinks that they're inadequate to the task.

I agree with this. The fact that he didn't even mention Solomonoff at all, even in passing, despite the fact that he devoted half the article to talking about induction, is strongly indicative of this.