News for hackers. Stuff that matters.
Re:Time Travel Simulation Resolves “Grandfather Paradox” by zrm on Wednesday September 03, 2014 @02:49AM (#8261799)
> 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.

But it still couldn't break a one-time pad.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by terhechte on Wednesday September 03, 2014 @03:33AM (#8261886)
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.

HPMOR is a really great book.

https://www.fanfiction.net/s/5782108/17/Harry-Potter-and-the...

Re:Time Travel Simulation Resolves “Grandfather Paradox” by Semaphor on Wednesday September 03, 2014 @05:36PM (#8265600)
fair warning: This, absolutely awesome and actually well written, fanfiction is by now longer than all the books combined.
Re:Time Travel Simulation Resolves “Grandfather Paradox” by eru on Wednesday September 03, 2014 @06:06PM (#8265735)
It's a decent read, but you have overlook that the author is very fond of himself.

Harry Potter and the Natural 20 is also highly enjoyable.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by Semaphor on Thursday September 04, 2014 @07:57AM (#8267699)
>that the author is very fond of himself.

How? And I found it better than the original at the very least ;)

Re:Time Travel Simulation Resolves “Grandfather Paradox” by eru on Thursday September 04, 2014 @07:58PM (#8271451)
Yes, it is a decent read. But it's a self-insertion Mary Sue fic. The author is very keen on telling you how smart he is. Very.

I do like his choice not to give the idiot ball to anyone.

(Please look up the technical terms on tvtropes. But only, if you have an afternoon to burn.)

Re:Time Travel Simulation Resolves “Grandfather Paradox” by maaku on Wednesday September 03, 2014 @04:33AM (#8262027)
Or, instead of receiving the next iteration you end up with a piece of paper with "DON'T MESS WITH TIME" written in your own shaky handwriting.

The space of possible stable outcomes is much larger than just the ones carrying the outcome of the computation.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by arethuza on Wednesday September 03, 2014 @09:36AM (#8262902)
Or maybe:

"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."

http://en.wikipedia.org/wiki/Singularity_Sky

Re:Time Travel Simulation Resolves “Grandfather Paradox” by possibilistic on Wednesday September 03, 2014 @04:58AM (#8262091)
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.)

Re:Time Travel Simulation Resolves “Grandfather Paradox” by wuliwong on Wednesday September 03, 2014 @11:50AM (#8263587)
Hah, funny, I had a similar question and I'm also in Atlanta. :)
Re:Time Travel Simulation Resolves “Grandfather Paradox” by tjhance on Wednesday September 03, 2014 @05:29AM (#8262167)
www.scottaaronson.com/papers/ctc.pdf

Shows that (with or without quantum computing) you can do all of PSPACE using a CTC (in polynomial time) and no more.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by mshron on Wednesday September 03, 2014 @09:36AM (#8262901)
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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by evanb on Wednesday September 03, 2014 @10:44AM (#8263212)
PSPACE is bigger than and contains NP. You still don't get ANYTHING=O(1), though.

https://en.wikipedia.org/wiki/NP_(complexity)#Relationship_t...

Re:Time Travel Simulation Resolves “Grandfather Paradox” by onion2k on Wednesday September 03, 2014 @05:24AM (#8262156)
It would probably bring Strong AI.

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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by wuliwong on Wednesday September 03, 2014 @11:41AM (#8263535)
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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by rst on Wednesday September 03, 2014 @09:20AM (#8262830)
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).
Re:Time Travel Simulation Resolves “Grandfather Paradox” by Houshalter on Wednesday September 03, 2014 @12:51PM (#8263940)
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.
Re:Time Travel Simulation Resolves “Grandfather Paradox” by phpnode on Wednesday September 03, 2014 @11:21AM (#8263434)
Using a time-loop in node.js to compute factorials https://gist.github.com/Marak/3967740
Re:Time Travel Simulation Resolves “Grandfather Paradox” by baddox on Wednesday September 03, 2014 @04:28AM (#8262013)
What algorithm would you run on this machine to yield strong AI?
Re:Time Travel Simulation Resolves “Grandfather Paradox” by DennisP on Wednesday September 03, 2014 @11:05AM (#8263324)
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."

http://wiki.lesswrong.com/wiki/AIXI

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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by zrm on Wednesday September 03, 2014 @04:53AM (#8262078)
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.

Or try simulating a human brain.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by baddox on Wednesday September 03, 2014 @05:11AM (#8262123)
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?
Re:Time Travel Simulation Resolves “Grandfather Paradox” by chriswarbo on Wednesday September 03, 2014 @10:26AM (#8263122)
AIXI-tl could use a CTC computer.

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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by TheLoneWolfling on Wednesday September 03, 2014 @12:12PM (#8263699)
Why are there so many accidents in our "reset button" lab?

But seriously, the problem with this is that it assumes that the only resolution to the CTC is that the AI generator tries another program.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by ww520 on Wednesday September 03, 2014 @03:51AM (#8261924)
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.
Re:Time Travel Simulation Resolves “Grandfather Paradox” by alcari on Wednesday September 03, 2014 @03:58AM (#8261941)
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.
Re:Time Travel Simulation Resolves “Grandfather Paradox” by acchow on Wednesday September 03, 2014 @04:01AM (#8261948)
You can't "break" a one-time pad because you can't possibly know when you've got the right "key".
Re:Time Travel Simulation Resolves “Grandfather Paradox” by tzs on Wednesday September 03, 2014 @04:37AM (#8262039)
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.

This also greatly simplifies backup systems.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by coldtea on Wednesday September 03, 2014 @05:15AM (#8262137)
>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.

Re:Time Travel Simulation Resolves “Grandfather Paradox” by pilsetnieks on Wednesday September 03, 2014 @06:32AM (#8262301)
Also known as rubber-hose cryptoanalysis (https://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis).
Re:Time Travel Simulation Resolves “Grandfather Paradox” by DSMan195276 on Wednesday September 03, 2014 @08:48AM (#8262696)
Obligatory xkcd: http://xkcd.com/538/
Re:Time Travel Simulation Resolves “Grandfather Paradox” by CocaKoala on Wednesday September 03, 2014 @11:06AM (#8263329)
Here's a message encrypted by a one time pad: "AHWAM"

The key is very short, only five letters, so it should be pretty trivial to brute force. Can you tell me what the message is?

Re:Time Travel Simulation Resolves “Grandfather Paradox” by kybernetikos on Friday September 05, 2014 @06:46PM (#8276710)
Was the one time pad HDDLC, or perhaps WJHLP or maybe BJENK or IEEOF?