As far as I'm aware complexity theory doesn't have it's own special definition of "infinite".
Just to be clear, I'm totally in agreement with you that a lookup table based AI would not actually be possible in the real world, but I don't think any sane person would claim that.
I didn't say infinite! I said "essentially infinite".
I would have used the exact term from complexity theory, except I don't know what it is for n! - the highest they have is EXPSPACE which is 2^n (which is smaller - much smaller).
I thought you said "pretty much infinite". Either way, neither "essentially infinite" nor "pretty much infinite" is a meaningful concept (I can just picture infinity, off at the nonexistent end of the number line, laughing at the puny numbers you describe as "essentially infinite"), so it'd be better to just rephrase it as "really really big", with as many "really"s as you feel is appropriate.
Just to be clear, I'm totally in agreement with you that a lookup table based AI would not actually be possible in the real world, but I don't think any sane person would claim that.