Universal Limits on Computation (2004) [pdf] | Hacker News Reader

Universal Limits on Computation (2004) [pdf]

arxiv.org

26 pointsanacleto9 comments

Wouldn't these computation limits get invalidated if some future advanced civilization / super-human AI came up with warp drives / could use wormholes / any other loophole around the speed-of-light?

If you could "pierce" speed-of-light limit, at least for signals, even with extraordinary costs, you may get some sort of distributed computing going on, potentially unbound (up to the size of full universe, as opposed to observable universe limited by light cones and expansion of space).

I liked Seth Lloyd's earlier paper better:

http://arxiv.org/abs/quant-ph/9908043

Are arXiv paper peer-reviewed? How are we sure that the papers are of quality?

Unfortunately, they are not. Submitters have to be vetted by somebody at some point, so the people who do submit should usually at least have a university affiliation (or have had one at some point), but that's a relatively low bar.

I don't know about physics, but in mathematics and theoretical computer science, there are really two problems that are not solved by arXiv:

1. We need a way to record mistakes in proofs / get an idea of the level of confidence in the proofs in papers.

2. There should be a way to collect papers of significance, to be able to get an idea of which papers are important.

Both are problems that have been solved in the past (more or less) by journals, and they are outside the scope of what arXiv is intended to provide. Nevertheless, there is still a lot of space for clever new models of open publishing, outside the traditional models. Unfortunately for the audience here, those problems are mostly social and political rather than technical (e.g., how do you break the influence of journals in academic hiring decisions).

Use your brain. Not kidding.

There's also a fun Wikipedia page on this:

https://en.wikipedia.org/wiki/Limits_to_computation

How to make sense for a CS grad. I was expecting something about Turing, Godel etc

A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/astro-ph/0404510, or http://arxiv.org/abs/astro-ph/0404510v2 for this specific version) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!

Ok, we changed the url from http://arxiv.org/pdf/astro-ph/0404510v2.pdf.

Reply on news.ycombinator.com