Abstract

From DeLoreans to police boxes and hot tubs, Science Fiction has provided many machines capable of time-travel. Whilst a powerful tool for learning from observation of other times, the causal flow of information can become somewhat distorted by the ability to send it back to before its generation. One question of time-travel that Science Fiction has not answered for us is whether or not there are any gains in computational power to be had by embedding a flux capacitor into the humble Turing machine.

Closed Timelike Curves describe a theoretical model of consistency for regions of space-time in the presence of time-travel. We shall discuss the uses of Deutschian CTCs in finding a solution to the Grandfather paradox and how to exploit the consistency requirements in circuit design allowing time-travel. In doing this, we shall cover some basic techniques used in complexity-theoretic analysis, define the complexity class P_CTC (problems that can be solved in polynomial time using circuits with CTCs) and prove that, rather surprisingly, this is equivalent to PSPACE .