In "Star Trek" and many other sci-fi series, "time travel" is a popular "sci-fi premise of the week" (just like "machines become self-aware," and "space pirates take over the ship").
But each sci-fi movie, and even each episode written by a different writer in the same series, tends to make up a different theory of time travel, and so each story tends to deal with time travel paradoxes in different ways.
I think most time travel stories can be categorized into a few basic time travel models (ignoring the physical methods of time travel: Starship-warp-10-slingshot/Guardian of Forever/time vortex/Stargate wormhole passing through a star/Delorean-with-flux-capacitor/steam-powered-clockwork H. G. Wells time machine/Skynet-generated time bubbles, etc.).
So here is my list of time paradoxes that should include just about every conceivable time travel story, whether in "Star Trek" or any other movie or TV show.
And the best way that I know to test the validity of any time travel theory is to throw the Grandfather Paradox™ at it, to see if it sticks. (If you go back in time and kill your grandfather, then you will never be born, but if you were never born, then who killed your grandfather?)
1. The Predestination Paradox (or causality loop)Definition: Everything the time traveler does in the past is already part of his history, so he never actually changes anything, and in fact the events in his own past were caused by his time travel, creating an endless loop of causality.
Examples: TNG's "Time's Arrow" (Data's 400-year-old head is found in a cave, Data later goes back in time, and he loses his head in a cave), Voyager's "Parallax" (the Voyager picks up a Federation distress signal from inside a singularity, enters the event horizon and becomes trapped, and sends out the same distress signal that originally caused it to enter the singualrity), the new Spanish film "Timecrimes" (a man keeps going back in time to prevent a crime, but keeps making it happen the same way, because his going back in time was already part of the events he had witnessed), "Escape From the Planet of the Apes" (in the future, Earth is ruled by talking apes; two apes travel into the past to when humans ruled Earth; their son is born and grows up to lead an ape rebellion, causing apes to rule Earth in the future), "Terminator 1" (the Terminator goes back in time, is destroyed, and its parts would be studied to later invent the Terminator; meanwhile, John Connor sent his own father back in time, who then impregnated Connor's mother, allowing Connor to be born and send his father back in time -- sort of a double Predestination Paradox with a reverse-Grandfather-Paradox twist thrown in), and "Terminator 3" (where the T-101 goes back in time to protect John Connor on Judgment Day, and his actions end up causing Judgment Day to happen just as he remembers).
Comments: This is the simplest and most internally consistent type of time travel story, where everything always happens once, including the time travel event, so history never changes. But it is a dramatically limited type of story, where the characters have no free will and cannot make informed choices, since they are typically ignorant of the fact that they have already done what they are planning to do in the past.
Grandfather-Paradox test: You cannot prevent your own birth in a Predestination Paradox; therefore you cannot kill your own grandfather. Any attempt to do so will be negated by "Fate" or a convenient story twist (e.g., you're aiming a gun at your young grandfather, about to pull the trigger, when a piano drops on your head; or you do shoot the guy you planned to, but later learn your grandfather had the same name as a guy who was shot by a time traveler -- as when the Terminator went through the phone book killing everyone named "Sarah Connor" in alphabetical order, but not the one he was trying to kill). The best illustration of the Predestination Paradox versus the Grandfather Paradox is in the "Futurama" episode where Fry goes back in time, accidentally kills his own grandfather, then accidentally has sex with his own grandmother, thus becoming his own grandfather (which is physically and biologically plausible, since Fry got half his DNA from his father, who got the same half of his DNA from Fry himself).
2. Creating alternate (or divergent) timelinesDefinition: When you go back in time, you create a new timeline that is different from the one you remember, so everything you do in that new timeline will lead to an alternate future different from the one you came from.
Examples: TNG's "Yesterday's Enterprise" (Lt. Yar goes back in time on the Enterprise-C to create a new timeline where the Federation was not at war with the Klingons), "Star Trek Generations" (the sun explodes, everyone on the Enterprise-D dies, and Picard enters the Nexus; with Kirk, Picard goes back in time and creates a new timeline where the sun does not explode, everyone on the Enterprise-D does not die, and Picard does not enter the Nexus) Voyager's "Timeless" (Old Chakotay sends a signal into the past to prevent the Voyager from crashing into an icy planet as he remembers), Voyager's "Endgame" (after returning to Earth after 20 years trapped in the Delta Quadrant, Admiral Janeway goes back in time and helps the Voyager get back to Earth immediately, allowing her younger self to be promoted to admiral 20 years earlier, as seen when Admiral Janeway at Starfleet Command calls Picard in "Star Trek: Nemesis"), "Terminator 2" (the T-101 goes back in time and breaks the causality loop that led to events in "Terminator 1," so that Cyberdyne could not use Terminator components to later invent Terminators), and "Terminator 3" (yes, this movie was listed under the Predestination Paradox for the T-101, but the T-X was creating an alternate timeline by going back and killing her future enemies when they were teen-agers), and "Primer" (where the time traveler wakes up early one morning, goes back in time to before he woke up, gives his sleeping self a sedative so that he doesn't wake up and get into the time maching, thereby creating a new timeline with two copies of himself, one a few hours older).
Comments: Like the causality loop, alternate-timeline stories are usually self-consistent, since the characters can do whatever they want in the new timeline, without any paradoxes, and with the further benefit that the time travelers do have free will, and need not be ignorant of their own past or be condemned to repeat it. However, once a time traveler creates a new timeline, he then often is stuck in that new timeline and can never get back to his original timeline.
Grandfather-Paradox test: If you go back to an alternate timeline, you are free to kill the man who would have been your grandfather in that timeline. Then he would be dead, and you'd be in a new timeline where another "you" will never be born. But it would not affect your own past.
3. Erasing your own past (with convenient memory insulation)Definition: There is only one timeline, and when a time traveler goes back and changes something, he erases his own past (and often himself), like erasing the image on an Etch-A-Sketch™ and replacing it with a new image -- both cannot exist together.
Examples: "Back to the Future" (when Marty prevents his parents from meeting, his image on a photo begins to fade away, as his own existence is being erased), "Back to the Future, Part III" (when Marty prevents Doc Brown from dying in the Old West, the photograph of Doc Brown's tombstone fades away, since the tombstone never existed), TNG's "All Good Things..." (Picard experiences a time paradox, but then acts to prevent the paradox before it started, thus going back to the start of the story where no one except him remembers the paradox), "Quantum Leap" (Dr. Becket would change his own past each week, creating new events to fill in his "Swiss-cheese memory;" in one episode, when he failed to save the younger version of his future associate Al, Al disappeared completely until Dr. Becket changed history and allowed Al to exist again in the future), and Voyager's "Year of Hell" (in which the Voyager crashed into and destroyed the Krenim timeship that had been changing the past, thus retroactively undoing every change it had ever made to the past, as if the timeship never existed).
Comments: The erasing-your-own-past scenario seems to be popular in many time travel stories, despite its questionable physical manifestations and convenient delayed-action self-erasure, allowing changes to be un-changed when their effects are undesirable -- this also leads to logical paradoxes and unexplainable plot twists (or continuity errors) in the story. It also leads to a lot of characters shouting, "We must repair the timeline before we are destroyed by a paradox!" or, "We must avoid a paradox at all costs!"
Grandfather-Paradox test: The erasing-your-own-past scenario is the very definition of the Grandfather Paradox, and was most directly addressed by "Back to the Future," in which the answer was: You will slowly fade away from a photograph taken in the future, then your physical body will start to fade away, but slowly enough so that you have time to reverse the paradox and "un-kill" your grandfather. (Which is to say, it doesn't address the paradox at all, it just avoids it.) Most of these erasing-your-own-past stories are primarily concerned with preserving the past and avoiding paradoxes.
4. Screwing up the past but then going back to fix it againDefinition: Like the erasing-your-own-past scenario, a new timeline is created, erasing events you remember, but you have the ability to go back and change the past again so that the future is "restored," or at least "close enough," to the one you remember.
Examples: "Back to the Future, Part II" (When old Biff goes back and gives his younger self the sports almanac, thus erasing his own past and the one Marty and Doc Brown remember, but then Marty and Doc Brown are able to go back and undo the changes, creating a new timeline that is similar to the one they rememeber), Stargate: SG-1's two-part episode "Moebius" (the SG-1 team goes back to ancient Egypt and screws up the timeline, so that there is no SG-1 team in that new future, but they leave a message for their alternate selves in that future of how to go back to the past and "un-screw-up" history, thus creating a third timeline where there is an SG-1 team again, and everything is almost the same as the original timeline), "Star Trek: First Contact" (the Borg go back in time, kill Zefram Cochrane, and assimilate Earth, but the Enterprise-E, shielded from the changes to the timeline, is able to go back, fight the Borg, and create a new future that is similar to the one they remember), TOS' "The City on the Edge of Forever" (McCoy goes back in time, prevents Edith Keeler's death, which causes the Enterprise and the Federation not to exist, but Kirk and Spock are able to go back in time and prevent McCoy from preventing Keeler's death, thus restoring the history they remember), "TimeCop" (where time police must go back and prevent time-traveling criminals from changing history, and if necessary, undo any changes the criminals have already made to the past).
Comments: The fixing-the-past scenario is popular in time travel stories, since it provides a built-in motivation for an unwilling time traveler to go to the past in the first place: to fix something he or another time traveler has changed. But like the erasing-your-own-past scenario, the stories are prone to physically questionable manifestations (like time travelers fading away) or convenient delays in self-erasure that allow the characters to become aware the past has been changed without being changed themselves, thus letting them go back and un-change the past.
Grandfather-Paradox test: You can go back and kill your own grandfather (or at least try), but that will cause a "time cop" to come back and prevent you from doing it, so that any paradoxes are only temporary and are eventually undone.
5. Time travel into non-causal realms of space-time (I'm sure there's a better "physics" term for this, like "non-intersecting light cones," but I can't think of it)
Definition: You can travel into the past, but you end up in a region of space so far away that you will never be able to meet yourself or change your own past.
Examples: "Back to the Future" (Marty plans to go back to the future 10 minutes before he left and warn Doc Brown that he will be shot, but when Marty gets to the future, his car breaks down and it takes him 10 minutes to reach Doc Brown, who is shot before Marty can reach him), the "Heroes" 2008 finale "Dual" (Daphne travels a few seconds into the past, but across the room, just in time to witness herself travel into the past from across the room, but not enough time to change anything) TOS' "All Our Yesterdays" (Spock is trapped during an ice age in the past of an alien planet, but he has no way of reaching anyone else in the Galaxy, so he is unable to change his own past).
Comments: This model of time travel is consistent with General Relativity and other theories of physics, but it is also the least interesting dramatically, since the time traveler can only go to a region in the Universe where he is too far away to change his own past, so it's like he never went to the past in the first place. However, this method also avoids any philosophical paradoxes.
Grandfather-Paradox test: If a time traveler goes back in time 100 years to kill his grandfather, then he will end up somewhere in the Universe more than 100 light-years away from his grandfather, and even if the homicidal time traveler fires a laser gun at his grandfather from that distant location, the beam will never reach his grandfather, or anyone else on Earth, until sometime AFTER the time traveler was born and went back in time. So no part of the observable Universe in the time traveler's past can be changed by anything he does in the part of the Universe he travels to.
This is just my brief list of five main types of time travel paradoxes, off the top of my head. If anyone can think of a time travel story or "Star Trek" episode that I have left out, feel free to add it to the list under one or more of the above categories (some time paradoxes overlap each other). And if I have left out some major category of time paradox, let me know -- I may have overlooked one.
