As far as I know, current cosmological models predict an infinite universe. This leaves me wondering, given our current understand of cosmology:

Can a hypothetical cosmological-scale computer keep expanding it's memory and perform an unlimited amount of operations?

By expand I mean the device might send probes to nearby galaxies, and use resources from those galaxies to produce more probes to other galaxies. Also produced is some kind of memory device and a communication relay, allowing it to function as a "memory expansion".

Such a device would be a true physical realization of a Turing machine!*

Limits I can think of are the 2nd law of thermodynamics and of course the speed of light. But perhaps if this device expands faster than the decrease of the rate of computation due to

1) Increasing entropy

2) Increasing device radius (the communication cost per step should be proportional to intergalactic distance)

can it still perform arbitrarily many operations?


*Here's an explicit construction.

A Turing Machine consists of four elements: an infinite tape, a read/write head, a finite state register and a finite instruction table.

Each galaxy stores a constant $k$ amount of bits, thus galaxies function as a tape. The probe contains the state register and optionally also the instruction table and head. Thus we have a Turing Machine, provided the probe doesn't run out of energy.


closed as unclear what you're asking by knzhou, ACuriousMind, Bosoneando, sammy gerbil, Norbert Schuch Aug 25 '16 at 23:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – David Z Aug 25 '16 at 5:55

The universe may or may not be infinite, we don't know yet. We know it is alsmot flat, but may be spherical. Maybe it is infinite, maybe not. But irrelevant. The universe we are part of, or anybody anywhere in it, is expanding and has a cosmological horizon. Outside that we never reach, going at c or lower. Thus you only have a finite set of galaxies you can reach. In fact, a finite number of particles, even counting photons. The number of baryons in the observable universe (which is bigger than our cosmological horizon), is about $10^{80}$ plus or minus a few orders of magnitude. Maybe you can store a bit or qubit in each. Add to that the number of photons, you could use them to store bits or qubits also. There's about $10^{10}$ photons for every baryon (protons and neutrons), so maybe you're at $10^{90}$ now. Add another factor of 25 because normal matter is only 4% of the universe, and maybe some other stuff, and you have about less than $10^{100}$ bits or qubits you can store. That is the max theoretical memory. Maybe once we know you'll have to add gravitons and a few other new field particles.

So still finite. Probably will need to reduce some of it so you can use it as your probe (read/write head) and energy to go around.

There is also a limit on time. The universe is accelerating and probably will lead to a heat death, I.e., maximum entropy. You need to do all this before that.

Alternately you could form (somehow, not divulging the secret) black holes with all the mass energy in the universe you can reach, except what you need to do your probes, and get to the Bekenstein limits, you'll need to transform my numbers to mass and get the area of the black holes, add them up or merge them all to get more, still finite. And figure out how to store the bits in each Planck area.

That is the theoretical limit, but I'm sure there are more constrained semi-theoretical limits based on how you can harness all that. And more constraints if you want to get a limit on number of bits/sec you can store or retrieve, and on basic ops/sec, those based on speed limits and your breakup of resources to be used for storage and for computation.

Good luck!

  • $\begingroup$ Thank you very much, this answers the question definitely -- I had forgot about accelerated expansion! Still a bit saddened that the universe provably does not allow this kind of construction, even knowing it wouldn't affect me in any way. $\endgroup$ – Real Aug 25 '16 at 6:31
  • $\begingroup$ Know what you mean. $\endgroup$ – Bob Bee Aug 25 '16 at 19:47

The fundamental limit on information that can be stored in a region of space is given by the Bekenstein bound. This bounds occurs when you have a black hole.

This bound can be seen in the following way. An observer in a Rindler wedge measures radiation with temperature $$ T~=~\frac{\hbar c}{2\pi gk}, $$ for $g$ the acceleration. This can connect to the black hole in the near horizon condition. The Killing vector $K_t~=~\sqrt{1~-~2m/r}\partial_t$ with $m~=~2GM/c^2$. The acceleration is computed as $g^2~=~\nabla^aK_b\nabla_aK^b$ which gives the acceleration $g~=~1/4m$ and the temperature of the black hole is $$ T~=~\frac{\hbar c^3}{8\pi GMk} $$

Entropy is related to heat energy by $\delta Q~=~T\delta S$ or for mass $Q~=~E~=~Mc^2$ that is also $TS$. This leads to $$ S~=~\frac{8\pi GM^2k}{\hbar c}. $$ For the Schwarzschild black hole the radius of the black hole is $r~=~2GM/c^2$ and so $M^2~=~r^2c^4/4G^2$ $=~Ac^4/16\pi G^2$, for $A$ the area of the horizon. This means $$ S~=~k\frac{Ac^2}{4G\hbar}~=~k\frac{A}{4\ell_p^2}, $$ where the area as $N$ Planck units of area $A~=~N\ell_p^2$ illustrates how a black hole can be thought of as $N$ qubits on the event horizon.

If you try to pack more information into a region than this all you do is create a black hole or a larger black hole. The qubits on the horizon are then elements of this "quantum gravity computer," which is a strange way to think of a black hole.

  • $\begingroup$ Thank you very much for the answer. However, the construction I provided does not assume you need to pack infinitely many bits into a finite space! That seemed to confuse others too. You could, as a thought experiment, store a single bit per galaxy (or solar system, etc). A probe would function as a read/write head and travel among galaxies altering the bit according to an instruction set. This is sufficient to conform the Turing Machine definition. $\endgroup$ – Real Aug 24 '16 at 22:05
  • 1
    $\begingroup$ @real But you specifically asked if it could be built. Just because this conforms theoretically to the definition (which I question too), does not mean it is physically possible. You've moved the goal posts. (And, no, I was not confused at all.) $\endgroup$ – Howard Pautz Aug 24 '16 at 22:24
  • $\begingroup$ @HowardPautz That's not my question. The question is if it can keep expanding and perform boundlessly many operations. I couldn't grasp a concrete impossibility proof from your statements. Can we continue discussing on chat? $\endgroup$ – Real Aug 24 '16 at 23:26

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