3 ms·

Universal Limits on Computation (2004) [pdf]

26 points by anacleto 11y ago

jestinjoy1 11y ago
How to make sense for a CS grad. I was expecting something about Turing, Godel etc
Sniffnoy 11y ago
A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/astro-ph/0404510 http://arxiv.org/abs/astro-ph/0404510, or http://arxiv.org/abs/astro-ph/0404510v2 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!
- dang 11y ago
  Ok, we changed the url from http://arxiv.org/pdf/astro-ph/0404510v2.pdf http://arxiv.org/pdf/astro-ph/0404510v2.pdf.
nickpinkston 11y ago
There's also a fun Wikipedia page on this: https://en.wikipedia.org/wiki/Limits_to_computation https://en.wikipedia.org/wiki/Limits_to_computation
scottlocklin 11y ago
I liked Seth Lloyd's earlier paper better: http://arxiv.org/abs/quant-ph/9908043 http://arxiv.org/abs/quant-ph/9908043
Rainymood 11y ago
Are arXiv paper peer-reviewed? How are we sure that the papers are of quality?
- nhaehnle 11y ago
  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).
- brobdingnagian 11y ago
  Use your brain. Not kidding.
bd 11y ago
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).

26 points by anacleto 11y ago

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 http://arxiv.org/abs/astro-ph/0404510, or http://arxiv.org/abs/astro-ph/0404510v2 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!

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

nickpinkston 11y ago

There's also a fun Wikipedia page on this: https://en.wikipedia.org/wiki/Limits_to_computation https://en.wikipedia.org/wiki/Limits_to_computation

scottlocklin 11y ago

I liked Seth Lloyd's earlier paper better: http://arxiv.org/abs/quant-ph/9908043 http://arxiv.org/abs/quant-ph/9908043

Rainymood 11y ago

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

nhaehnle 11y ago
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).
brobdingnagian 11y ago
Use your brain. Not kidding.

bd 11y ago

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