The undecidability of the halting problem is a formalization of the grandfather paradox.
Consider a “perfect oracle”, which can predict Earth’s state indefinitely far forward, down to the atomic level. It can easily be used as a time machine. Just make a room, put up a sign saying “Messages to the past here”, and then predict that room’s future state. Indeed, an oracle is more powerful than time machines, since it can see messages future-dwellers don’t want it to see.
Of course, the problem with perfect oracles is that one can see what one will do in two minutes, and then decide not to do it, creating a paradox. Equivalently, John Smith Jr. could write “John Smith Sr., don’t marry that woman!” in the time-room, causing his father not to marry, and himself not to be born.
Formally, consider John Smith Sr. as a Turing Machine. He wants to know whether he’ll halt at some future point (or what John Smith Jr. will think of his marriage, or any number of other things). Suppose he can. But then, he could write code saying “if we run forever, halt; if we halt, run forever”. Contradiction, so it’s impossible.
The Rationalist Conspiracy 