> In the presence of CTCs, quantum mechanics allows one to perform very powerful information-processing tasks, much more than we believe classical or even normal quantum computers could do
That seems like an understatement if I'm understanding it correctly.
Imagine you have a "time machine" and you want to solve some arbitrary computable problem. You try a prospective solution and see if it's correct. If not, you send the next prospective solution back to be tried on the next go around the time loop. Once you arrive at the correct solution, you send that same solution back so that the iteration stops there. Then the loop repeats indefinitely with the correct solution so that the probability of exiting the loop at the correct solution approaches infinity.
It would literally be the end of the world as we know it. P=NP. Forget about quantum cryptography, that would break all public key cryptography, all cryptographic hash functions. It would obsolete algorithmic complexity theory by effectively turning every finite space algorithm into an O(1) algorithm. It would probably bring Strong AI.
There's a chapter in the brilliant fan fiction "Harry Potter and the Methods of Rationality" where Harry gets access to a Time-Tuner, i.e. a time machine from the Harry Potter universe, and this is the first experiment he envisions and performs.
"I am the Eschaton; I am not your God.
I am descended from you, and exist in your future.
Thou shalt not violate causality within my historic light cone. Or else."
It wouldn't be a constant energy algorithm though, would it? For each successive optimization iteration, you would have to expend energy. Does that energy get put back with every rewind of the clock? If so, energy is also infinite.
I wonder what the time-energy-complexity trade-offs are?
As an aside, I would gladly pay someone to walk me through the math and physics sometime. (Any grad students in Atlanta are more than welcome to take me up on that offer... I might even try Skype.)
This is the key result in this conversation; this should be higher. Basically: if we insists on Deutsch's causal fixed point propety of CTCs, they do not give you P=NP, they give you P=PSPACE. That is, all problems which can be solved in polynomial space can now be solved in polynomial time, and vice versa.
So for a time-travel computer to give P=NP or P=O(1), it would have to violate Deutsch's causality criterion. I have almost zero knowledge of either field, but it sounds to me like it makes Deutsch's model more plausible.
A CTC is effectively a computer that can process a loop instantly, regardless of how complicated it is. Given that, we could design an AI machine that could analyse an arbitrary amount of data in any depth without regard to how long it'll take. More than that, everything happens in one 'tick' of whatever is controlling the CTC, so there aren't any issues around asynchronous processing. It just 'goes away'. Such a machine would never have to wait for another process to finish. Strong AI would be pretty much a certainty - we'd be able to brute force any problem.
I wonder if you'd run into some sort of energy problem. Like, this time machine would require some sort of energy and incur some amount of wear and tear on during each pass. The amount of possible solutions to today's cryptography might make this brute force level of effort, even with a time machine, infeasible. I feel like nasty old thermodynamics may preserve our world still. :)
Granted, I'm way way out of my depth here. I have a Ph.D. in physics but I studied nonlinear oscillators, relating them to problems in neuroscience.
Beyond P=NP: this actually gives you a constant-time solution for any problem where it's possible to enumerate candidate solutions, regardless of how long it takes to do so. So, we'd have ANYTHING=O(1).
Only if you are certain there is a correct answer. If there isn't a correct answer, you just cause a paradox. It's also more likely that the machine will spontaneously fail, or the creator will get hit by a bus before he can complete it, etc.
You could do AIXI: "The AIXI formalism says roughly to consider all possible computable models of the environment, Bayes-update them on past experiences, and use the resulting updated predictions to model the expected sensory reward of all possible strategies."
So you could use the time loop to run through this algorithm.
But what's this about predictions? Why predict when you have a time machine? All you really need is a reward function and this algorithm:
- Get a message from the future with its best-ever reward and how it achieved it.
- Try something else
- When you get to the future, see whether you've done better than the best ever. If so, replace the best ever.
- With each iteration keep a count. If you've reached some maximum number of tries without improving the best score ever, do the best strategy one last time and quit.
It might be tricky figuring out the best span of time to use, and whether you can do mini-loops within bigger loops somehow.
First you need a rigorous formal definition of strong AI. Then write a computer program that iterates over all possible computer programs until it finds one that meets the definition.
I can't think of any formal definition of strong AI that's very satisfying. You could certainly make a great chess or Go machine, and do a lot of AI tasks, but can you think of any reasonable formal definition of a strong AI?
As well as performing arbitrary computations in one tick, we could also keep a CTC going as a "reset button": whenever we realise that an incorrect/sub-optimal decision has been made, we can go back to when we started.
This lets us 'brute force' our real-world interactions (ie. our IO), as well as "merely" gaining an infinite computing speed-up.
This could be exploited by something similar to the "Success Story Algorithm" http://www.idsia.ch/~juergen/directsearch/node13.html . The CTC-AI would some way of "scoring" the world (ie. a fitness function), some probability of modifying its decision-making policy, and some non-zero probability of resetting the world. If the reset probability is anti-correlated to the world's score, worlds which score higher over time are more likely, hence the machine's decisions are more likely to increase the score than decrease it, hence the policy is more likely to improve over time.
One-time pad is just a generated key used once. The "time machine" will break it by trying out all keys in the key space in the time loop. If time is not an issue, brute force method pretty much breaks any crypto.
One-time pads are still secure because the decryption process will produce every plaintext the same length as the ciphertext, and you'll have no way of knowing which one was correct.
Others have explained why that does not work. The way you'd use backward time travel to crack a OTP is to wait until the recipient of the message decrypts it, then your steal the decrypted message, then you go back to the time where you wanted to break the code and give yourself the message.
Another use for backward time travel is data compression. To compress a file, you simply replace its contents with a note saying when you did this. When you later want the file, just pop back to that time and get it.
>Others have explained why that does not work. The way you'd use backward time travel to crack a OTB is to wait until the recipient of the message decrypts it, then your steal the decrypted message, then you go back to the time where you wanted to break the code and give yourself the message.
That's not actual decryption. You can do the same thing without time travel too, e.g by hitting the guy.
That seems like an understatement if I'm understanding it correctly.
Imagine you have a "time machine" and you want to solve some arbitrary computable problem. You try a prospective solution and see if it's correct. If not, you send the next prospective solution back to be tried on the next go around the time loop. Once you arrive at the correct solution, you send that same solution back so that the iteration stops there. Then the loop repeats indefinitely with the correct solution so that the probability of exiting the loop at the correct solution approaches infinity.
It would literally be the end of the world as we know it. P=NP. Forget about quantum cryptography, that would break all public key cryptography, all cryptographic hash functions. It would obsolete algorithmic complexity theory by effectively turning every finite space algorithm into an O(1) algorithm. It would probably bring Strong AI.
But it still couldn't break a one-time pad.