Yeah, you obviously can't code for infinite possibility, so it just has to be robust enough. And the first step would be text-based. "I walk into the tavern" "There's a fight happening / it's now owned by someone else / bartender asks if you want the usual" kind of thing. Biggest hurdle is having a persistent and cohesive world.

Given the advancement of image/song/code generation, I think it's not out of the realm of possibility for a game to be truly limitless. Just not remotely any time soon.