17
$\begingroup$

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

However there is a finite amount of atoms in this service 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?

$\endgroup$
34
$\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.

$\endgroup$
  • 10
    $\begingroup$ @AaronRoth I was stuck in a black hole. Accepted now. $\endgroup$ – Good Person Jan 26 '14 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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