1 Iki Piki: {referring to Death of Insanely Overpowered Fireballs, who is still standing nearby} He killed that AI thing from the past. Will that have any effect on history?
2 Spanners: It doesn't generate any causality paradoxes. Our past is fixed, so it actually already happened.
3 Spanners: It just means the entity stopped working on someone's computer. Any user with half decent writing skills should be happy about it.
4 {scene change: The past. To be precise, the office where Will Shakespeare works.}
4 Shakespeare: {at his computer} Hey, where'd Clippy go?! I need help with Chapter 9!

Time travel is of course rife with the potential to cause all sorts of causality paradoxes. One solution is that what is in the past has happened, and nothing you can do can change it in any way. Under this assumption, if you travel back in time to kill your grandfather before he sires your father, then no matter how you attempt to achieve it, you fail - simply because history tells you that he did sire your father.

This is actually one of the most workable methods of resolving time travel paradoxes in science fiction and in roleplaying gaming. Obviously you exist... so obviously your grandfather must have lived to sire your father.

Or did he?

If the only evidence you have is the word of your grandmother, then maybe she was lying about who your grandfather really was. So if you go back and kill the guy who she says is your grandfather, you might be able to do it after all. Without causing a paradox, because he wasn't really your grandfather...

In this form of time travel, research and irrefutable proof of events in the past become important. Anything that has been recorded is likely to have really happened. Unless the recording was faked by time travellers...

You see, this form of rigid and inflexible past is quite interesting in terms of developing a time travel story. Probably moreso than a world in which you can change the past - and where you don't have to worry about making things consistent.

---

2014-04-05 Rerun commentary: I remember one time travel roleplaying game I ran, which used a different method of resolving time paradoxes. Changing the past could change the present, but only probabilistically, forcing the present to collapse into either the present we all know and love, or an "evil" alternate present. Change a few things, and there's no major effect, but change a bunch of things and the present flips into another stable state.

Anyway, in this game the adventurers were given the task of ensuring that the Treaty of Waitangi was duly signed on the day as recorded in the history books, to foil the plot of some evil time agents who wanted to prevent it, thereby enhancing the probability state of their own dystopian present. (It all makes sense in context.)

Anyway anyway, as was virtually inevitable, the treaty got destroyed in a fire or explosion or somesuch. So the PCs solved the problem by returning to the present, retrieving the original treaty document from a museum, and then going back to the past with it and leaving it near the remains of the explosion, so that it could be found and recovered, thus setting up a stable time loop of sorts. (The main problem being that the document would age by roughly an additional 150 years every time it passed through the loop, and eventually become infinitely old. We just ignored this detail.)

Wow, that was a fun adventure. It's generally best not to worry too much about damaging history in such games, lest it get in the way of actually having fun.