The concept has not always had this name, that is more recent branding. ~25 years ago it was formalized by a proof that optimal generalized learning is a universal sequence prediction problem. An unfortunate property of universal sequence prediction problems is that they are profoundly intractable and we really don't have a good idea of how to reduce these problems to a tractable approximation on real hardware.

Many basic concepts in computer science are in this class: data compression (see: the Hutter Prize), indexing (see: "learned indexing"), cache replacement algorithms (see: Bélády optimality theorem), etc. We narrowly specialize these algorithms such that they look very different to be computationally feasible but at the limit they are the same algorithm problem.

I find it interesting that database engines are essentially a giant bucket of algorithms all in this class.

Same, and it led me discover there was already a wikipedia article about it: https://en.wikipedia.org/wiki/AI-complete