assuming proof of np-complete* self-consistent time loops: grab any other variable that is not fixed and stuff your defiance into it. you’re going to kill your parents? extend their lifespan. you’re going to kill your parents before mom gives birth to you? prepare to resuscitate them, try ensure that if this happens it only happens right before giving birth, try to ensure you can survive your mom dying in childbirth, get cryonics on hand (depending on how far back you are). if your attempt to avoid it is naturally upstream of the event occurring, then entropic time is now flowing backwards with respect to this variable. set up everything that is still flowing forwards so that you get a variable setting that is least unacceptable.
* I think, anyway. are self-consistent time loops np-complete? halting oracle? they definitely resolve p = np as “true on a time-loop computer”: before running check and time looping, set answer = answer + 1 unless test passes. (and then you simply need a computer that is stronger than the force of decay induced by the amount of computer-destroying lucky events you’re about to sample.) so that gives you all np problems. so yup np-complete. are they halting oracles?
We ask, and answer, the question of what’s computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid grandfather paradoxes. Our main result is that computers with CTCs can solve exactly the problems that are Turing-reducible to the halting problem, and that this is true whether we consider classical or quantum computers. Previous work, by Aaronson and Watrous, studied CTC computers with a polynomial size restriction, and showed that they solve exactly the problems in PSPACE, again in both the classical and quantum cases.
Compared to the complexity setting, the main novelty of the computability setting is that not all CTCs have fixed-points, even probabilistically. Despite this, we show that the CTCs that do have fixed-points suffice to solve the halting problem, by considering fixed-point distributions involving infinite geometric series. The tricky part is to show that even quantum computers with CTCs can be simulated using a Halt oracle. For that, we need the Riesz representation theorem from functional analysis, among other tools.
We also study an alternative model of CTCs, due to Lloyd et al., which uses postselection to “simulate” a consistency condition, and which yields BPP^path in the classical case or PP in the quantum case when subject to a polynomial size restriction. With no size limit, we show that postselected CTCs yield only the computable languages if we impose a certain finiteness condition, or all languages nonadaptively reducible to the halting problem if we don’t.
assuming proof of np-complete* self-consistent time loops: grab any other variable that is not fixed and stuff your defiance into it. you’re going to kill your parents? extend their lifespan. you’re going to kill your parents before mom gives birth to you? prepare to resuscitate them, try ensure that if this happens it only happens right before giving birth, try to ensure you can survive your mom dying in childbirth, get cryonics on hand (depending on how far back you are). if your attempt to avoid it is naturally upstream of the event occurring, then entropic time is now flowing backwards with respect to this variable. set up everything that is still flowing forwards so that you get a variable setting that is least unacceptable.
* I think, anyway. are self-consistent time loops np-complete? halting oracle? they definitely resolve p = np as “true on a time-loop computer”: before running check and time looping, set answer = answer + 1 unless test passes. (and then you simply need a computer that is stronger than the force of decay induced by the amount of computer-destroying lucky events you’re about to sample.) so that gives you all np problems. so yup np-complete. are they halting oracles?
You may be interested in Scott Aaronson et al’s paper on the subject of computability theory of closed timelike curves