Grandfather Paradox

This is the famous grandfather paradox.
Lets say that the time traveller goes back in time a hundred years and kills his grandfather when his grandfather is only a little boy. What happens?
On one hand if the grandfather was killed when he was a little boy, there is no way he could have been a grandfather, and so the time traveller could not have been born. On the other hand if the time traveller had not born, the grandfather would not have died....

The grandfather paradox is the classic example of the paradoxes and problems inherent in time travel.

Here's the form in which I first heard it:

Three men are sitting together, and one of them announces "Right now, in my basement, I have a working time machine!" One of the other men wants to use it, and being asked why, explains that he had always hated his grandfather, who had abused his grandmother and ruined her life. "I have always regretted," he said, "that my grandfather died of old age before I was a grown man and could kill him for what he did to her. If I could travel back in time to before they met and kill him, not only could I avenge my grandmother, but I could save her from having to ever endure him."

The first man, not being very smart despite having invented a time machine, agrees to this, and the other man goes back in time with a rifle to the night before his grandparents met.

Two men are sitting together, and one of them announces "Right now, in my basement, I have a working time machine!" . . .

That's the way my father told it, and I seem to remember his saying that he had read it as a short story in a sci-fi book a long time ago. It seems to have an antique flavor, which makes me think there is an ur-version out there, but nobody who mentions it seems to have any sources. Perhaps it did spontaneously generate in the common knowledge.

The whole story strikes me as very Freudian, but someone else can elaborate on that . .

The paradox, of course, is that having killed his grandfather before his parent was concieved, he was never born, and so he didn't go back in time, and so his grandparents married, and so he was born, and so he went back in time, and so he killed his grandfather, and so he was never born, and so on.

There are many solutions put forth for the paradox, which I try to cover here, in a spectrum from most physical to most metaphysical, with the major problems with each one:

1. Time travel leads to paradoxes, and therefore is not possible.
   Objection: Modern physics seems fairly certain that time travel is possible, at the very least at the subatomic level, and probably happens all the time. Besides, this answer is no fun.
2. Time is not linear, but a series of branching possibilities, and all outcomes of any choice exist: The Multiple-Timelines hypothesis
   Objections: Beloved as they are of writers of speculative fiction, multiple universes are frowned on by physicists at the moment. Besides, this really doesn't satistfy us from a human perspective: Sure, there are infinite timelines, in some of which the man exists and in some of which he doesn't, but does he exist in our timeline?
3. Time travel cannot be invented; if the man kills his grandfather, ripples of that change ocsilate back and forth through history until a change occurs that prevents the first man from inventing the machine. Then there is no longer any paradox and history becomes stable again. (I didn't explain this one very well: Think about it a little, and if your brain doesn't explode, it might make sense.)
   Objections: This solution is itself a paradox! (I think) Besides, it's no more fun than the first one, once you've untangled it.
4. You can't cause paradoxes: Varying implementations, from the Morphail effect to the Novikov principle. Basically, if he goes back in time, something will happen to prevent him from actually doing the deed. Perhaps a virtual particle, appearing for an instant, will knock the bullet off course just enough; perhaps he will be violently expelled either back to his own time or into oblivion; perhaps something in between, but anyway the entire universe will be conspiring against him. This can be implemented as a variant of 3: The timeline oscillates until a causality is reached where the paradox never happened.
   Objections: This seems to require a universe that is actively and intelligently trying to prevent paradoxes- a thing for which we have no explanation, justification, evidence, or mechanism, (unless we assume it evolved that way; or use the mechanism of 3, which carries with it all of 3's objections)
5. Traveling in time removes one from causality: If he goes back in time and kills his grandfather, he was never born; but by removing himself from the normal timeline, he no longer has to be born; he just is. If he goes back home no one will remember him, and he may or may not lose his memories of a past that never happened, but he still exists, because he's outside time.
   Objections: Perhaps the most fun of all the suggestions so far. Of course one gets tangled up in what causality is and creative physics and whether anything can be known if causality doesn't really apply, but none of that can really be reasoned about. No real mechanism for this one either.
6. Paradoxes simply don't matter: This is the one that the story above illustrates. If he kills his grandfather, he doesn't exist. That's that. But the grandfather's still dead. Beloved of writers who don't want to bother explaining anything.
   Objection: But it doesn't explain anything!
7. There are more things in heaven and earth: So there's a paradox. So what? If we weren't temporal beings ourselves, that wouldn't bother us. All the confusion is caused by our limited minds. Basically, this means that whatever happened didn't seem odd to any of the people involved, but whatever really happened is beyond their comprehension.
   Objection: Yeah, and if you believe that, I have some psychotropic drugs to sell you. Seriously, this one can't be argued against because it's basically a deus ex machina. Not much fun for the same reason it's hard to argue against.
8. We are such stuff as dreams are made on: Paradoxes like this just prove the nonexistence of objective reality. Rather, all universes and timelines are merely creations of sentience and none is "realer" than another. Therefore, as long as the man who killed his grandfather believes that is what he did, he did; since there is no specific reality the illogic doesn't matter.
   Objections: Dream on, sister.

There. I think that covers about everything.

Of course, everyone knows that the real solution is that anyone who would go back in time solely to kill his own grandfather is a bastard anyway . . .