The Best Computer Ever
By Tim Farage
The fastest
computer nowadays can do about a few trillion computations per second, and has
a few gigabytes of memory. Not too
shabby. But is there a way to determine
what the Best Computer Ever could do? If
so, this would allow us to have some idea what we would be able to compute in
the future, and to know what will forever be beyond our computational
reach.
To imagine what our
Best Computer Ever could do, we need to realize that every computation that is
done will change some of the bits that make up memory, and that after the
computation is completed the computer's memory will hold the answer. So the amount of memory available will affect
the computational resources at our disposal.
Also, the rate of computation (measured as the number of possible bit
changes per second) will certainly affect what we can compute. And lastly, so does the total amount of time
that a program is allowed to execute. So
the three main variables that determine how much we can compute are 1) the
amount of memory, 2) the speed of the computer, and 3) the amount of time the
computer is allowed to execute a program.
How then do we try
to determine what the Best Computer Ever can compute (measured as the number of
possible bit changes that could occur while a program is running)? After all, we don't know what breakthroughs
in physics, engineering, software, etc. will occur. Well, lets' go for broke. For our Computer's memory let's use all of
the matter in the Universe! Can't do much better than this. How much matter is there? Astrophysicists think that there are a few
hundred billion galaxies in the Universe, and that each galaxy has, on average,
a few hundred billion stars. Since we
know the average size of a star, and we can estimate the amount of matter not
found in stars, astrophysicists have come up with a figure of about 1080 elementary
particles (electrons, protons and neutrons) in the entire Universe. Let's also assume that each elementary
particle can store a bit of information.
So at any moment in time, our Computer can hold 1080 bits of
information.
During a
computation, the contents of memory changes, so the faster we can change
memory, the more computations we can perform. Is there a limit to rate of
computation? Yes, and it's determined by
what is called a 'Plank time'. This is the theoretically shortest moment of
time that is possible - there can be no changes that occur faster than a Plank
time. Fortunately, a Plank time is very
short, around 10-43 seconds.
If we assume that our Big Computer can compute at the maximum possible
rate, then it will be able to do 1043 computations per second. In case this doesn't seem fast to you, this
number means that Best Computer Ever can do 10 million million
million million million million million computations per second!
How long shall we
let the Best Computer Ever run in order to do our bidding? Let's again take the best possibility; let's
run it for the entire time our Universe has existed - about 14 billion years,
which is about 1018 seconds.
So if we take our Computer, which is made using all the matter in the
entire Universe and operates at the fastest possible speed, and runs for the
duration of the life of the Universe so far, it would be able to compute about
1080 x 1043 x 1018 = 10141
bits. Just to be safe, let’s multiply
this by a billion. We now have a
Computer that can do up to 10150 bits of computation. Now this is a tremendous number. In words it's about a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion.
Given this huge
number, shouldn't this be enough computing power to compute anything that's
possible to compute? Actually, there are
lots of problems that are too big for the Best Computer Ever! For example, suppose you're a chess player and you'd like to know for certain what the
best first move is for White. Maybe it's
Pawn to King Four or Pawn to Queen Four, or maybe some other move. So you ask the Best Computer Ever to check
out every possible chess game and report back the best move. Sorry Charlie, but the Best Computer Ever
won't make a dent in the problem, even if it ran for the entire time our
Universe existed. It's estimated that
there are around 10600 chess games; this is so much bigger than 10150
it would give an
There are lots of
problems like this that are too big for our Best Computer Ever. Ever heard of the Traveling Salesman
Problem? Here's a brief description of
it. Suppose a salesman named John is
supposed to go to a number of cities in order to sell a certain widget. He is given a table that has these cities and
the distances between them. For example,
suppose the cities are Dallas (D),
|
D | C
| N |
A
D | 0 | 1000 | 1800 | 600
C | 1000 |
0 | 700 |
1100
N | 1800 | 700
| 0
| 500
A | 600 | 1100
| 500 | 0
Of course, John
would like to know the shortest route to take that starts and ends in
Let's do one last
example of Big Computer's limitations.
Suppose you got onto a Star Trek website and found a picture of Captain
Kirk fighting with Spock. Let's say the
resolution is 300 x 400 pixels (not that good) and that it's in black and
white. Thus there are 120,000 pixels that are either on or off. Now you ask Best Computer Ever to randomly
generate pixel values that create black and white pictures and stop when it
generates the picture of Captain Kirk fighting with Spock. You could let the Computer run until our
Universe fades away, and a billion more universes after that, and almost
certainly you won't randomly generate the Kirk/Spock picture.
So here's the
point: No matter who, no matter where and no matter
when, there will always be problems that best computers will never be able to solve.
Tim Farage can be emailed at tfarage@hotmail.com. His biography is available at http://www.utdallas.edu/~tfarage/bio.html.