Suppose that every atom in the known universe had a unique serial 
number. Suppose I picked a serial number at random, and then asked you 
to go find out where that particular atom is. (Let us assume that there 
is no particular correspondence between serial numbers and position in 
space.)

Well your first problem is going to be that if I pick a random serial 
number, that atom is probably many billions of light years away from 
Earth, and so even if you knew where to go, you couldn't possibly go 
there. But suppose you somehow have access to an electronic database of 
all the atoms, their serial numbers, positions, and other interesting data.

(We casually ignore for the moment the minor detail that a database 
describing the known universe would obviously be very much larger than 
the actual universe itself, and hence could not possibly exist inside it...)

Given such a database, there are two ways you could try to find this atom.

One is to simply go through the database table, one row at a time. This 
is equivilent to examining every atom in the universe, one by one, until 
you find the one you want.

Assuming that you could somehow examine several million million million 
records per second (highly implausible), to find the atom you're looking 
for would take... several tens of billions of times the current age of 
the universe. As in, after all the energy in the universe had been spent 
and the entire cosmos had died an icy death of silent stillness at zero 
entropy, your hypothetical computer would still have not made 1% 
progress yet.

Just stop and think about that for a moment. There literally isn't 
enough time in the universe to perform this search. Woah.

(But hey, you're searching all the atoms in existence! It's hardly 
surprising...)

Alternatively, you could perform an index lookup. Assuming you have an 
index on the main table that consists of a tree with 10 entries in each 
node, you could find the atom in question after examining... 100 nodes. 
(If we assume the tree is well-balanced.) Even if we type in the index 
node requests by hand, it will take well less than 10 minutes to find 
out atom.

So, one way has O(n) complexity, and would take so long that there 
simply isn't enough time or energy in the universe to complete the 
computation. The other way is O(log n), and would take less than 10 
minutes even if done partially by hand.

Wow. Just... wow.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Alternatively, you could perform an index lookup.

  It's enough for the values to be sorted. Then you can simply perform
a binary search. Assuming fast random access the search should take
much less than a second.

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> (We casually ignore for the moment the minor detail that a database
> describing the known universe would obviously be very much larger than
> the actual universe itself, and hence could not possibly exist inside it...)

Asimov solved this long ago!
http://www.multivax.com/last_question.html

:)

> Assuming that you could somehow examine several million million million
> records per second (highly implausible), to find the atom you're looking
> for would take... several tens of billions of times the current age of
> the universe.

BTW, what if when you finally reach the area the atom was at originally it
already moved on to an area you had already inspected?  concurrency problems?
:)

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Invisible <voi### [at] devnull> wrote:
> > Alternatively, you could perform an index lookup.
>
>   It's enough for the values to be sorted. Then you can simply perform
> a binary search. Assuming fast random access the search should take
> much less than a second.
>
> --
>                                                           - Warp

Today, the number of atoms of the observable universe is estimated at about
10^80. (See http://en.wikipedia.org/wiki/Observable_universe).

Whish it were my bank account! But presently only the absolute value is correct
....

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Invisible <voi### [at] devnull> wrote:
> > Alternatively, you could perform an index lookup.
>
>   It's enough for the values to be sorted. Then you can simply perform
> a binary search. Assuming fast random access the search should take
> much less than a second.
>
> --
>                                                           - Warp

Today, the number of atoms of the observable universe is estimated at about
10^80. (See http://en.wikipedia.org/wiki/Observable_universe).

Whish it were my bank account! But presently only the absolute value is correct
....

Post a reply to this message

Invisible wrote:
> Suppose that every atom in the known universe had a unique serial 
> number. Suppose I picked a serial number at random, and then asked you 
> to go find out where that particular atom is. (Let us assume that there 
> is no particular correspondence between serial numbers and position in 
> space.)

I don't want to spoil your gedanken experiment, but in modern physics 
you can not distinguish one (e.g.) hydrogen atom from another. It is not 
that they are two different objects that are not marked so you can not 
distinguish them, but much more fundamental. If you exchange two protons 
nothing happens. There is no way to figure that out, because there is 
absolutely no difference. You probably better say that this one proton 
is at all these places at the same time.

Perhaps you know the interpretation that a positron is just an electron 
flying backwards in time. It has been suggested that if the universe 
ends in a big crunch (probably not) then you only need one electron 
weaving forwards and backward in time. i.e. if an electron and a 
positron annihilate, what actually happens is that the electron changes 
direction again. So probably not true, but a funny image anyway.

Post a reply to this message

andrel wrote:
> I don't want to spoil your gedanken experiment, but in modern physics 
> you can not distinguish one (e.g.) hydrogen atom from another.

You say this, but it's not actually true.  You cannot distinguish two 
hydrogen atoms as long as you ignore the stuff that lets you distinguish 
them.  Like, say, their positions.

Certainly the hydrogen atoms in my coffee are distinguishable from the 
hydrogen atoms emitting light eight minutes ago in the sun.

Basically, science has a list of "things it's safe to ignore when 
replicating an experiment."  Given that list, hydrogen atoms are 
indistinguishable. But there's still a list.

It's like saying "pennies are indistinguishable, from a spending point 
of view. I can replace one penny with any other penny."  Yet I'll still 
get arrested for putting all your pennies in my bank account.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> Alternatively, you could perform an index lookup.
> 
>   It's enough for the values to be sorted. Then you can simply perform
> a binary search. Assuming fast random access the search should take
> much less than a second.

Indeed. A binary index lookup and a binary search are equally efficient.

However, inserting a record for a new atom becomes somewhat 
compute-intensive if we have to keep all the data in sorted order. (If 
it's a typical array-like structure, O(n) complexity again. For an 
index, it's just O(log n) - assuming any rebalancing you choose to do 
doesn't blow it up.)

Of course, whether you have an unordered table and seperate index or 
whether the index *is* the table doesn't matter too much. (Depending on 
just how much data you store per atom...)

Post a reply to this message

Actually, the real problem would be that electronic representation of the 
atomic data would require atoms for storage purposes....So you'd have to 
have the database operating outside the space/time continuum to begin 
with. :-)

Jim

Post a reply to this message

andrel wrote:
> Invisible wrote:
>> Suppose that every atom in the known universe had a unique serial 
>> number. Suppose I picked a serial number at random, and then asked you 
>> to go find out where that particular atom is. (Let us assume that 
>> there is no particular correspondence between serial numbers and 
>> position in space.)
> 
> I don't want to spoil your gedanken experiment, but in modern physics 
> you can not distinguish one (e.g.) hydrogen atom from another.

Sure. You're probably right. And anyway, how the heck would you write 
serial numbers on them, even if you could? More to the point, how would 
you catelogue them all in a giant database? And what if they move 
around? What if an atom is created or destroyed? etc.

My point is really just the staggering difference between complexity 
classes, rather than physical correctness. The same argument would apply 
to *anything* that there's 10^100 of - atoms in the universe is about 
the only [remotely] comprehensible way to describe just what a big 
number that is. ;-)

Post a reply to this message