1
$\begingroup$

There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a classical computer if the number of operations needed to be performed for solving them is exceeding the total number of atoms in the observable universe. [1]

Now, it's pretty clear that in terms of space you have the total number of atoms in the observable universe as an upper bound, but how is it also an upper bound for computation time or number of instructions?

Update: A computer with memory of X bits can have a total of 2 to the power of X states, so in case X theoretically equals to the total number of atoms in the observable universe, the upper bound for computation time would actually be 2 to the power of the total number of atoms in the observable universe, which is a lot more than the total number of atoms in the observable universe. In fact, a computer can actually count the total number of atoms in the observable universe using only about 266 bits.

$\endgroup$
  • $\begingroup$ By convention. In other words, "the number of atoms in the universe" is just another way of saying "a big f***ing number." $\endgroup$ – Rick Decker Oct 31 '18 at 15:21
  • $\begingroup$ It is an astronomical number -- literally. IIRC it's around $10^{80}$ when the age of the universe (since the big bang) is estimated to be $10^{19}s$. So, even if a computer could run at $10^{40}$ flops (which is already insane), we would still need to wait for a long time to count the atoms in the universe. $\endgroup$ – chi Oct 31 '18 at 16:09
  • $\begingroup$ For running time, I much prefer to use something like the number of instructions a computer running at 1GHz could have executed since the big bang. I share your scepticism that the number of atoms in the universe is any kind of a bound on running time, except insofar as it's a really really big number that has some physical significance. $\endgroup$ – David Richerby Oct 31 '18 at 18:07
  • $\begingroup$ @Moon, give us a link of such a textbook. I agree with you that this comparison is somehow counterintuitive. I think a more intuitive comparison would be to compare time steps or time of execution for infeasible problems with universe age or multiples of universe age $\endgroup$ – Curious_Dim Nov 1 '18 at 1:14
  • $\begingroup$ "how is it also an upper bound of time or electronic interactions in a processor?" Do you really mean a different question (whose meaning seems elusive and ambiguous to me) from the one in the title? $\endgroup$ – Apass.Jack Nov 1 '18 at 4:19
2
$\begingroup$

Let us assume an explicit range of the number of atoms in the universe to make sure that we are talking about the same thing. It is estimated that there are between $10^{78}$ to $10^{82}$ atoms in the known, observable universe. In other words, it is a number between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion atoms.

Is the number of atoms in the universe large enough?

The common unit of computing performance is one floating point operation per second (FLOPS, flops or flop/s).

  • How much is the total computing capacity worldwide today? According to a popular estimate, "computing capacity worldwide was probably around 2 x $10^{20}$ – 1.5 x $10^{21}$ FLOPS, at around the end of 2015".
  • Extrapolating that by a generous 50% yearly growth rate, the total computing capacity worldwide today, around the end of 2018 is less than 6 x $10^{21}$ FLOPS.
  • Suppose you can run the total computing capacity worldwide today continuously for 100 billion years (which is much longer the life span of our universe as commonly estimated by physicists), you would have done a whopping 6 x $10^{21}$ (seconds) x 3.1536 x $10^{19}$ (Flop/s) $\approx$ 2 x $10^{41}$ FLOPs.
  • Suppose everyone of about 7.6 billion people on the earth is enjoying the same computing journey and there are another 100 billion planets like earth, we would have done a total of 2 x $10^{41}$ x 7.6 x $10^9$ x $10^{14}$ $\approx$ 1.5 x $10^{65}$ FLOPs.
  • However, that number is still much less than a billionth of the number of atoms in the universe! If each FLOP would count as 1, we need much more computing device and time to count the number of atoms in the universe!

Even given the impossibly optimistic yearly doubling of computing capacity worldwide, we would still need tens of years before our total computing ability to be anywhere near the number of the atoms in the universe.

Why choosing the number of atoms in the universe?

As Rick Decker indicated in his comment, that number is about the easiest way to say a big but fathomable number just about right to convey the message of practical un-computability. The vivid image of an immensely large universe filled with one of the smallest particles brings immediate understanding of an otherwise unfathomably big number to all walks of people.

Another nice huge number, Google, $10^{100}$, is sort of void of concrete meaning.

Further Topics

Which project is the largest computing project that has been completed or is going on?

Does FLOP capture all kinds of computing power? For example, quantum computing?

Why is the number of atoms is a really very small number compared to the number of combinations that we have to deal with routinely in many practical computations?

$\endgroup$
1
$\begingroup$

There are two physical bounds:

  1. If you could implement a single bit of memory using one single atom (which we are nowhere near achieving), then total memory in the universe would be limited by the number of atoms in the universe, so we have a physical upper bound for the amount of state that a computation can ever have.

  2. From quantum physics we know there is a minimum amount of energy required to make any change to any system. Take the total mass of the universe, apply $e = mc^2$, divide by the minimum amount of energy required for any state change, and you have an upper limit for the total number of state changes that a computation can ever have.

I can't think of any problem where the amount of state is a problem, but there are many especially cryptographical problems that cannot be solved due to the second restriction. And of course total mass of the universe is limited by number of atoms.

$\endgroup$

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.