Not only that, but you could make an RPG (table top or not) that lacked all of those except story
Story is 100% irrelevant for being classified as an RPG.
Many RPGs don't have one, many roguelikes come to mind (which are a sub-category of RPGs). You just start at dungeon level 0, reach dungeon level 100 to win. If there is a story, it is background, an excuse to get going and has no impact at all on gameplay.
And
game genres really must be defined according to
gameplay.
You are right on track with the idea that computer RPGs have to have something in common with PnP RPGs.
But the essence here is the abstraction. It isn't the player doing any action, it is the character - resolved by the game's systems and/or a real GM.
You don't even need a story for PnP RPG - sure, it would make for one horrible PnP session, but it could be done. What it cannot be done without is the abstraction.
I argue that story is necessary for a pencil and paper game because my ultimate definition of one is that it is an activity that is at the same time storytelling and playing a game (with the extra restriction that people receive a role to play rather than playing as narrators or what have you; without this restriction you would have a story game).
However, by storytelling, I don't necessarily mean the kind of story you would read in a novel. I agree with you that you could play D&D without much contextualising. You could, if you want, start the game in the dungeon. There doesn't need to be a backstory of how you got there, any kind of specific quest or even a backstory to the dungeon. And you are right, the game would be less interesting this way, but still an RPG. However, it would be an RPG because the game still has a "story", namely, that of the players working their way through the dank and gloomy dungeon. There is still an imaginary gameworld that goes beyond the numeric representation of all the other stuff in game. The players can still solve their problems by using these, maybe they can kill a monster that would otherwise be immune to their weapons by knocking down a statue in the dungeon over it. Maybe they can lure that poisonous blob they found in room 31 into the cauldron in room 57, close the lid and light the fire under it! Etc, this imaginary environment is the story in this case. An RPG without any story in this loose sense would be a completely abstract game and I think it shouldn't be called an RPG, even if its mechanics were completely analogous to GURPS or D&D.
Now, taking this to computer games, my point is that computer games can only do this by approximation. You cold have a dungeon crawler where you could do the examples with statues and the cauldron. But only because a designer thought beforehand of adding that (or even because a physics system is present). But not because the game is reacting to the storytelling, which is impossible with a computer.
Even in computers a game without story in this meaning wouldn't be called an RPG. You mention rogue-likes, which I find interesting because it was a roguelike that helped me see things this way. I used to play Dungeon Crawl Stone Soup a lot. In one run, I was playing a summoner and I managed to enter a fortress of some race or other. There were knights, soldiers and whatnot in the fortress, and I was having some difficulty. At one time, I found myself surrounded by zombies and most of my imps dead, so I ran away trying to thin then out so I could summon again. However, as I ran, I began to realise they weren't attacking; and taking a minute to check on them, realised they obeyed me! The zombies had been created by one of my imps (I didn't know they could do that).
The point of the story is that... that is the story! The dungeon crawl, the finding out about a new ability after entering a sinister castle and my character's subsequent quest to conquer the world with demonology powered necromancy ended up being a cool story exactly because DC:SS is (or at least was) a good CRPG.
By the way, I agree that this abstraction of using the PC skills instead of the player's can be helpful tool, but this can't be total otherwise there would be no gameplay. I mean, people are ok with having your aim and strength depend on numbers on the character sheet. But if the battle tactics depended on intelligence and the dialogue options were selected based on moral attributes or whatever, to the point the player didn't have any more input other than setting up his character, it wouldn't be a game at all, but a simulation.
The issue here is that having a character sheet helps a game be more RPG like because those attributes become tools the designer of the game can use to come up with interactivity based on how the character is different, which is obviously something that brings it closer to PnP games. This puts a disadvantage on action games that try to emulate RPGs (beside the aspect that no table top game is an action game). But even with this disadvantage, it is possible to make an action game that still is deeply associated with RPGs. Taking my Bloodlines example, Bloodlines succeeds in being an RPG on a lot of things, but fails badly when it comes to combat (both at being an RPG and at being a good FPS). DS succeeds well in making a good action gameplay that is responsive to the PC the player creates, but eschews RPG in almost all other of its aspects (NPC interaction, exploration, etc). Of the two, I think Bloodlines succeeds at being closer to RPG games more, since a lot more of the game is dominated by non combat stuff, while in DS, while combat is much of the game, it is too limited to allow it to catch up with Bloodlines.
) or the truly infinite possibilities. But the other core elements, the abstraction and mental/cerebral influence, remain.
