What are the limits of computation in this universe?

Question

I understand that Turing completeness requires unbounded memory and unbounded time.

However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$ is irrational there is no way to store more than a certain number of digits even if all the atoms in the universe were used for this purpose.

What then are the limits of computability of an implemented Turing machine (which could use all the resources of the universe but no more) based on the limits of the universe? What is the maximum number of digits of $\pi$? Are there any papers on this subject that might be interesting to read?

Possibly related topic: Can a computer simulate itself as part of a simulated world. — Sadeq Dousti, Feb 26 '11 at 08:32
There is a fun essay by Scott Aaronson on this: http://www.scottaaronson.com/writings/finite.html — Artem Kaznatcheev, Feb 26 '11 at 08:57
You might be interested in the discussion around this question. Yarosloav Bulatov posted a link to a popular-science version of the Lloyd paper Peter Shor linked to below, but, unfortunately, the link appears to be broken now. I read that paper at the time, but didn't save it, and don't remember the exact title. — Aaron Sterling, Mar 26 '11 at 17:11
How do you know there is a bounded amount of atoms in the universe? — Andrej Bauer, Aug 17 '20 at 13:13

score 36 · Accepted Answer · edited Jul 18 '15 at 09:15

Seth Lloyd has a paper on the subject. You need energy to compute, but if you put too much energy into a small region, it forms a black hole. This slows down time (making the time it takes for the computation to complete relatively longer), and any computation done in the interior of a black hole is wasted, as the results cannot be extracted from the black hole and used. Seth calculates the limits on the amount of computation possible, and shows that for some measures of computation, the most computationally intensive environment possible in the universe would be that surrounding a black hole.

@AaronRoth I was stuck in a black hole. Accepted now. – Good Person Jan 26 '14 at 16:42 — Good Person, Jan 26 '14 at 16:42

What are the limits of computation in this universe?

1 Answers1