親殺しのパラドックス
親殺しのパラドックス（おやごろしのパラドックス）は、タイムトラベルにまつわるパラドックスで、SF作家ルネ・バルジャベルが1943年の著作 Le Voyageur Imprudent（軽はずみな旅行者）で最初に（この正確な形式で）描いた。英語では grandfather paradox（祖父のパラドックス）と呼ぶ。すなわち、「ある人が時間を遡って、血の繋がった祖父を祖母に出会う前に殺してしまったらどうなるか」というものである。その場合、その時間旅行者の両親のどちらかが生まれてこないことになり、結果として本人も生まれてこないことになる。従って、存在しない者が時間を遡る旅行もできないことになり、祖父を殺すこともできないから祖父は死なずに祖母と出会う。すると、やはり彼はタイムトラベルをして祖父を殺す……。このように堂々巡りになるという論理的パラドックスである。
このパラドックスは当事者の誕生の不可能性にだけ注目したものではない。むしろまず第一に、時間を遡るタイムトラベルを不可能にするあらゆる行為を考慮している。パラドックスの名称は単にそのような様々な行為の代表例にすぎない。他に、タイムマシンの発明に繋がる科学知識を特定し、その時代に遡って（殺人などの手段で）その科学者の仕事を妨害してタイムマシンが発明されないようにするという例がある。
哲学においてはこれと等価なパラドックスが autoinfanticide と呼ばれていて、時間を遡って赤ん坊時代の自分自身を殺すというものである。
このパラドックスは時間に逆行するタイムトラベルが不可能だとする証拠として使われてきた。しかし、パラドックスを避けるための様々な仮説も提案されてきた。例えば、過去は決して改変できないという考え方では、祖父や親を殺そうとしてもその試みは失敗し、相手は必ず生き延びるとする。あるいは、過去へのタイムトラベルは別の時間線を生み出すだけで、その時間旅行者が生まれた時間線はそのまま残っているという考え方もある。
ノヴィコフの首尾一貫の原則
イゴール・ノヴィコフの首尾一貫の原則とキップ・ソーンは、時間を遡るタイムトラベルがパラドックスの危険を冒さずに可能となる一つの見方を提示した。その仮説によると、唯一の可能な時間線は完全に首尾一貫しているものだけであり、時間旅行者が過去に遡って行う行為はすべて歴史の一部であって、首尾一貫性を崩すようなパラドックスとなる行為は決して実行できない。いわゆる決定論と呼ばれる考え方であり、自由意志という観念とは矛盾する。つまりこの考え方でいけば、過去へのタイムトラベルが可能だとしたら、歴史によって個人の行動が決定されることになる。
並行宇宙
パラドックスを防ぐアイデアとして、時間旅行者は元々の歴史とは異なる並行宇宙に行くのだと解釈するもので、上の科学的理論で述べたのと同じ考え方であり、SFにもよく見られる。歴史改変SFにあるタイムトラベル参照。
例えば、村上もとかの漫画作品『JIN-仁-』は、正体不明の人物のタイムスリップに巻き込まれ、現代医師の南方仁が幕末期にタイムスリップして、未来の医療技術を持ち込むという話である。主人公の南方仁は、幕末期では精製不可能な抗生物質を入手するため、再び現代へとタイムスリップし、また幕末期へと戻っていく。その際、現代にタイムスリップした際に自分自身と出くわし、その自分自身をタイムスリップに巻き込んでしまう。つまり冒頭の正体不明の人物は、南方仁本人であった。その2度目のタイムスリップにおいて、現代の南方仁は、「幕末期に南方仁がタイプスリップした事によって、歴史が改変されたもうひとつの現代」にタイムスリップする。つまり、南方仁がタイムスリップで飛ばされる先が2種類ある事で、2つの平行世界が成立している。
過去は変えられない
ノヴィコフの首尾一貫の原則に対応した解釈では、過去に遡っても自然の法則（あるいは他のなんらかの要因）により、そのタイムトラベルがなかったことになるような如何なる行為も防がれるとする。例えば、祖父を撃とうとしても銃弾が外れたり、そのような行為の成功を妨げる何らかの事象が発生する。歴史を改変しようとする時間旅行者の行為は常に「不運」に見舞われ失敗に終わるか、何らかの偶発事によって失敗に終わる。結果として時間旅行者はもともと知っている歴史を改変することができない。小説などでよくあるのは、時間旅行者が単に防ごうと思っていた事象の発生を防げないだけでなく、偶発的にその事象の発生を助けてしまうというパターンである。
この考え方では自由意志の存在が疑われ、人間に自由意志があるというのは幻想だとされたり、少なくとも限度があるとされる。またこの場合、因果性は常に守られると仮定している。すなわち、原因がなければ結果は存在し得ないとする。一方で、原因が取り除かれてもその結果生じた事象はそのまま存続するという解釈もある。
それと密接に関連する別の解釈として、時間線には自己修復能力があるという考え方がある。時間旅行者の行為は大きな湖に石を投げ込むようなものだとする。すると波紋が広がっていくが、間もなく波は消えて何事もなかったかのようにもとの状態に戻る。例えば、時間旅行者が自国を悲惨な戦争に導いた政治家を暗殺したとする。するとその政治家の周囲の者がその暗殺を口実として戦争へと突入し、暗殺への一般大衆の感情がカリスマの死を相殺することになる。あるいは時間旅行者が恋人が交通事故で死ぬのを防いだとしても、別の原因（階段を踏み外す、食事をのどに詰まらせる、流れ弾に当たるなど）でその恋人が結局死ぬことになる。2002年の映画『タイムマシン (2002年の映画)』では、主人公は恋人が強盗に殺されたため、それを防ぐためにタイムマシンを作るが、その恋人は交通事故で死んでしまう。未来へと旅立った彼は、タイムマシンでは恋人を救えないし、救えるとしたらタイムマシンを作ることができなかっただろうということを学ぶ。時間旅行者が過去に遡るきっかけとなった事象は変えられないとする物語、どんな改変も「修復」されるとする物語、あまりにも大きな改変は修復できないとする物語などがある。『ドクター・フー』のロールプレイングゲーム (en) では、時間は水の流れのようなものだと説明している。その流れにダムを作ったり、方向を変えたり、せき止めたりすることは可能だが、低いほうへと流れる全体的方向を変えることはできない。
時間旅行者が過去を変えたのか、歴史を覚えている通りに促進させたのか、はっきりしないこともある。例えば、作品が一つしか現存していない芸術家がいて、時間旅行者がその芸術家のところに行き、他の作品を隠しておくよう説得したとする。元の時間に戻ったとき他の作品を一般に知られていたとしたら、時間旅行者の計画が成功したとわかる。しかし戻ってから一週間後に他の作品が発見されたとしたら、彼の計画が歴史を変えたのか、それとも単に歴史がその通りに進行するのを助けた（つまり彼が隠すよう説得したため、これまで他の作品が見つからなかった）だけなのか不明である。
宇宙が消滅する
SF小説にはパラドックスを生じさせると宇宙が消滅する、あるいはそのパラドックスに影響された時空間の一部が消滅するという例もある（前者の例として『サマータイムマシン・ブルース』、後者の例として『戦国自衛隊1549』が挙げられる）。その場合、パラドックスを防ぐことがプロットの中心となる。例えば、『新スタートレック』の最終話がある。
それほど破滅的でない類似の解釈として、歴史が改変されるかどうかで時間旅行者の死が関わってくる。例えばバック・トゥ・ザ・フューチャーシリーズの1作目では、過去を変えてしまったために主人公の存在が消えてしまう危険が生じ、自身の存在をかけて過去を修復しようとする。この解釈では、祖父を殺した場合、殺人者までの存在は全て消えてしまい、祖父の死も別の原因だったことになる。従って歴史的観点ではパラドックスはなかったことになる。
過去の改変は取り消される
この解釈は他の解釈とも部分的に似ている。タイムトラベルが可能ならば親殺しのパラドックスを生じさせるような行為は不可能だとし、タイムトラベルそのものを取り消すようないかなる行為も不可能だとする。そのような行為はそれを取り消すような結果を生じ、関係者の記憶も書き換えられてその事象がなかったことになる。そして、過去を変えられるとしたら、その改変が必要なものだったということだと解釈する。
例えば、過去に遡って親を殺そうとしても失敗する。一方、別の誰かの死を防ぐために過去に遡って無作為に選んだ人々に何かをした場合、その行為は取り消されず成功する。なぜなら、タイムトラベルの理由やタイムトラベルそのものがパラドックスを生じないためである。
さらに、歴史上の大事件に関するような改変の場合、それがタイムトラベルを不可能にするような改変でない限り成功する。その場合、その時間旅行者が改変を行うと即座に本人のその事象についての記憶や知識が書き換えられる。
例えば、1887年のオーストリアにタイムトラベルした時間旅行者が無作為に選んだ5人の人間を殺し、その中に偶然アドルフ・ヒトラーの親が含まれていたとする。するとヒトラーは存在しないことになるが、その改変がタイムトラベルの存在を否定するものでない限り、そしてそのタイムトラベルの理由を否定するものでない限り、改変はなされる。しかし、その時間旅行をすることになった理由に影響が生じる場合、改変はできない。何者かが別の人間に過去に遡って特定の人間を（誰と明かさずに）殺させるという企みは成功しない（取り消される）。なぜなら、成功するとそもそも殺人を依頼する動機がなくなってしまい、タイムトラベルが行われないことになるからである。
この解釈をユーモラスに描いたエピソードがアニメ『フューチュラマ』にある。主人公のフライが過去にタイムトラベルし、うっかり祖母と結婚する前の祖父を死なせてしまう。取り乱した祖母はフライを誘惑し、もとの時間に戻ったフライは自分が自分の祖父だということを知る。
過去改変の試みは織り込み済み
藤子・F・不二雄の「ドラえもん」には、「現在は過去を改変しようとする未来からの干渉を織り込んだ上で成り立っている」とする話がある。てんとう虫コミックス37巻「のび太の0点脱出大作戦」では、のび太がテストでいい点を取るために出木杉の答案を見ようとテストが返却された後の未来へタイムマシンで移動するが、そこにはのび太本人が待っていて、「他人の答案を見て百点とろうなんてせこいこと考えるなよ。実力でいこうよ」と言って、答案を見に来たのび太を撃退してしまう（この時点ではドラえもんにものび太にもなぜ出木杉の部屋にのび太がもう一人いたのかまったく不明）。のび太は仕方なく自力で勉強を始め、それなりの点を取って周囲から褒められる。自力での成果に気をよくしたのび太は、翌日に出木杉の部屋に過去の自分が答案を見に来ることを思い出し、過去の自分を撃退するためにドラえもんにひみつ道具を借りて出木杉の部屋へタイムマシンで向かう。この話では、のび太が過去の改変に成功したようではあるが、のび太は「出木杉の答案を見た現在」を変えるために過去に行ったわけではない。
また32巻「連想式推理虫メガネ」では、金貨が密室から消えたという事件を解決するためにドラえもんとのび太がタイムマシンで金貨がなくなった時間帯の密室に張り込むが、犯人はついに現れずドラえもんは金貨を持ち出して現在に戻り持ち主に返そうとする。つまり「ドラえもんが過去にさかのぼって金貨を持ち出したから金貨が消えた」というオチなのだが、オチが描かれるまでの間は完全に「謎の金貨消失」としてストーリーが展開している。
なお、藤子・F・不二雄の場合の「SF」は「すこし・ふしぎ（Sukoshi Fushigi）」の略。
谷川流の小説、「涼宮ハルヒシリーズ」では、1巻よりも未来の主人公、キョンによってもたらされた過去への干渉によって現在が成り立ち、現在のハルヒやSOS団との活躍が描かれる。作中、「過去に干渉して未来を変えることはできない」と語られているが、「干渉できず、変わらない」と言う意味ではなく、干渉した結果が未来の姿である。作中では「規定事項」と呼ばれており、未来人は自由に渡航することはできない。