= 27d567bc2d48d9f40e9ccc20ea370b15)
NoSuchPlace comments on Open thread, 16-22 June 2014 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (172)
Have a program use its own output as input, effectively letting you run programs for infinite amounts of time, which depending on how time travel is resolved may or may not give you a halting oracle.
Also you can now brute force most of mathematics:
one way to do this is using first order logic which is expressive enough to state most problems. First order logic is semi-decidable which means that there are algorithms which will eventually return a proof for correct statements. Since your computer will take at most ten seconds to do this, you will have a proof after ten seconds or know that the statement was incorrect if your computer remains silent.
To expand on this: Moravec's classic "Time Travel and Computing".
What practical benefits or effects on the world do I get out of my new infinite computing power and mathematical proofs? Presumably i can now decrypt all non-quantum encryption, and do various high cost simulations very fast.
It helps with simulation of quantum mechanics, but I don't think that it helps with most classical simulations.
As Eugine mentions, there is a concrete way to use time travel to solve NP problems, those where you can recognize the answer if you have it. In fact, it is possible, under one formalization, to use it to solve a class of problems called PSPACE, which just means problems that you could solve with unlimited time, but limited memory, the obvious guess when NoSuchPlace says "infinite time." But look up the method Eugine mentioned - it isn't obvious how to extend it.
I don't know any applications of PSPACE problems, because they are impractical, but NP problems come up all the time and there is a big industry of solving examples on the edge of practicality. People often do this by converting them to SAT, the universal NP problem and then apply "SAT solvers"; so googling something like "sat solver applications" gives various suggestions, such as microchip design. Of course, if you really could solve SAT problems, you'd use much larger examples that people don't even bother with today. And if you could really solve PSPACE problems, you'd try even more exotic things.
It won't give you a halting oracle without an infinite computer. The best it can do is effectively give you 2^n computing time, where n is the number of bits in memory.