Ya I was just thinking that the simplest learning algorithm would actually be something simpler like "solving systems of equations as a matrix" (I'm feeling lucky Google result):

https://www.mathsisfun.com/algebra/systems-linear-equations-...

So you enter your inputs and outputs in a big table and solve by brute force to get an algorithm. It might not be an interesting one, or one useful beyond that one problem, but it's something.

There are also some graphical techniques for truth tables (boolean-value matrices):

https://www.allaboutcircuits.com/textbook/digital/chpt-8/log...

And this is kinda sorta loosely related to classification algorithms like k-means clustering, at least that's how my brain associates them:

https://en.wikipedia.org/wiki/K-means_clustering

Anyway, I view neural networks as a way of solving a huge matrix with gradient descent (hill climbing) as the optimization technique. It fundamentally will always struggle with the local minimum (maximum) problem just like in calculus.

Whereas genetic algorithms bust out of that mental trap via random sampling. I'm sure there's a proof out there somewhere that says they can solve any problem, given enough time, which is why I view them as the basis of learning. As I write this with my neural net hmmm..

To me, the only way forward is at the meta level, quantum computing or similar (as you very astutely pointed out).

An analogy for this might be that the vast majority of us do our daily work on the imperative side of programming (Turing machines) without realizing that they can be made equivalent to the vastly simpler functional side of programming (Lambda calculus) that solved most of the problems we face today 50+ years ago.

The state of the art when I first starting following this in the late 90s was optimizing neural nets evolved via genetic algorithms. I never heard anything else about it, but keep in mind that shortly after that, HP bought Compaq, private industry research spending cratered, native mobile app programming buried the innovation of declarative and data-driven programming that the web popularized, single page apps made web development untenable, video cards ended CPU innovation, and wealth inequality directed us all into nursing CRUD apps back from the brink of death instead of making contributions to open source projects that could fundamentally advance the human condition.

The problems are so widespread and entrenched now that if we can even break past a few of them, then I see rapid and transformative change potentially happening very quickly. It's like how the forces that be work to make sure that nobody gets UBI, because we can't have the plebeians enjoying the same return on investment that the wealthy take for granted. No, everyone must be kept poor and struggling or else they might just find the time to automate themselves out of a job.

Edit: sorry I just realized that I contradicted you on search. I was trying to make the point that if you could fit the whole search space into a matrix, then we could just solve it. Since that's not possible for most real-world problems, then yes I agree with you that search is actually the fundamental problem-solving algorithm.