Hacker News Reader

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

fair warning: This, absolutely awesome and actually well written, fanfiction is by now longer than all the books combined.

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.

>that the author is very fond of himself.

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

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

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.

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

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

Hah, funny, I had a similar question and I'm also in Atlanta. :)

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.

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.

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

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.

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.

Using a time-loop in node.js to compute factorials https://gist.github.com/Marak/3967740

What algorithm would you run on this machine to yield strong AI?

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.

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?

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.

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.

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.

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.

You can't "break" a one-time pad because you can't possibly know when you've got the right "key".

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.

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

Also known as rubber-hose cryptoanalysis (https://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis).

Obligatory xkcd: http://xkcd.com/538/

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?

Was the one time pad HDDLC, or perhaps WJHLP or maybe BJENK or IEEOF?