20
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Possibly related topic: Can a computer simulate itself as part of a simulated world. $\endgroup$
    – Sadeq Dousti
    Commented Feb 26, 2011 at 8:32
  • 7
    $\begingroup$ There is a fun essay by Scott Aaronson on this: scottaaronson.com/writings/finite.html $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Feb 26, 2011 at 8:57
  • 5
    $\begingroup$ Apt: scottaaronson.com/thesis.html $\endgroup$
    – user4379
    Commented Mar 24, 2011 at 23:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Commented Mar 26, 2011 at 17:11
  • $\begingroup$ How do you know there is a bounded amount of atoms in the universe? $\endgroup$
    – Andrej Bauer
    Commented Aug 17, 2020 at 13:13

1 Answer 1

Reset to default
37
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 12
    $\begingroup$ @AaronRoth I was stuck in a black hole. Accepted now. $\endgroup$
    – Good Person
    Commented Jan 26, 2014 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.