Novikov self-consistency and computability

Question

The Wikipedia article on the Novikov self-consistency principle has a section on time loop logic, where it discusses using time travel to solve any NP problem by finding an algorithm where the only consistent outcome is the solution.

For example you could have an algorithm as follows:

To find a factor of a number $n$:

1. If you receive a message from the future with a number y, and y is a factor of n, set x = y

2. If you receive a message from the future with a number y, and y is not a factor of n, set x = (y + 1) mod n

3. If you receive no message from the future, or an invalid message, set x = 1

4. After 1 hour send x back into the past.

The only self consistent outcome is that you immediately receive a message from the future with a factor of n.

But couldn't you use this same technique to create a scenario where there are no possible consistent outcomes? E.g. always send back a different number to the one you received?

Ergo there must be some reason why this setup isn't possible. In which case why do we assume it would work for problems that do have a consistent outcome?

Answer 1

Novikov's idea was that you just can't do that; it's a law of physics that history is consistent. This short speech of his sets it out in more detail; here's the key part:

As for the constraints of ‘free will’, the reader should notice that even without a time machine, ANY LAW OF PHYSICS places limits on ‘free will’. Say, I might wish to walk on the ceiling (without special equipment): my ‘free will’ prompts me to. This, however, is forbidden. The law of universal gravitation limits my ‘free will’ and there is nothing I can do about it. In the presence of the time machine the constraints on ‘free will’ are, of course, somewhat different, but they are not, in principle, anything extraordinary in the physics of our time.

I.e., every time you try to run an inconsistent algorithm, something will go wrong—most probably the most likely thing that could go wrong, such as an electrical glitch or cosmic ray leading to computation of the wrong value. When you run a consistent algorithm, something can still go wrong, but there's also a nonzero chance (probably fairly large) that it will compute what you want it to compute.