Novikov Self-consistency Principle - Time Loop Logic

Time loop logic, coined by the roboticist and futurist Hans Moravec, is the name of a hypothetical system of computation that exploits the Novikov self-consistency principle to compute answers much faster than possible with the standard model of computational complexity using Turing machines. In this system, a computer sends a result of a computation backwards through time and relies upon the self-consistency principle to force the sent result to be correct.

A program exploiting time loop logic can be quite simple in outline. For example, to compute one prime factor of the natural number N in polynomial time (no polynomial time factorization algorithm is known in traditional complexity theory; see integer factorization):

1. If N is 0 or 1, abort.
2. Allocate a communication channel c.
3. Receive one prime factor, F, of N from the future on channel c.
4. Test that F ≠ N, that F divides N (time complexity O(log N)), and that F is prime (polynomial time; see AKS primality test).
   1. If so, send F backwards in time on channel c.
   2. If not, send F + 1 backwards in time on channel c. Note that this results in a paradox, as the number received in step 3 above is not the same as that sent in this step.

The self-consistency principle guarantees that the sequence of events generating the paradox in the nested conditional has zero probability. Note that if N is itself prime, i.e., there is no such prime F ≠ N, then some event will prevent the execution of step 3 that receives the value F from the future. Assuming the machine executing the program itself continues to function, it can detect this failure and abort.

Physicist David Deutsch showed in 1991 that this model of computation could solve NP problems in polynomial time, and Scott Aaronson later extended this result to show that the model could also be used to solve PSPACE problems in polynomial time.