BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Closed Timelike Curves and Complexity Theory - William Simmons\, S
 t Catharine's College
DTSTART:20161130T193000Z
DTEND:20161130T200000Z
UID:TALK69455@talks.cam.ac.uk
CONTACT:Matthew Ireland
DESCRIPTION: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 informat
 ion 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 pow
 er to be had by embedding a flux capacitor into the humble Turing machine.
 \n\nClosed Timelike Curves describe a theoretical model of consistency for
  regions of space-time in the presence of time-travel. We shall discuss th
 e uses of Deutschian CTCs in finding a solution to the Grandfather paradox
  and how to exploit the consistency requirements in circuit design allowin
 g time-travel. In doing this\, we shall cover some basic techniques used i
 n complexity-theoretic analysis\, define the complexity class P_CTC (probl
 ems that can be solved in polynomial time using circuits with CTCs) and pr
 ove that\, rather surprisingly\, this is equivalent to PSPACE.
LOCATION:Wolfson Hall\, Churchill College
END:VEVENT
END:VCALENDAR