On Tue, 17 Dec 1996 James Rogers <jamesr@best.com> Wrote:
>I could calculate 5203^127, albeit pretty slowly.
And find the prime factors? You wouldn't have the time, The Big Crunch,
The heat death of the Universe or Tipler's Omega Point would happen first.
>for every single bitwise operation, I could show you
>exactly what process is going on in the ALU at a transistor
>by transistor level.
For any single bitwise operation you could, for every single bitwise
operation you could not.
>Actually, I think that arithmetic computation is a really
>poor example of something that we don't (can't) understand.
>It is a simple, deterministic process. There are no unknown
>variables.
Even humble Arithmetic is full of mystery and weirdness. For example, I'll
bet it would take you less than 5 minutes to write a computer program that
would search for the smallest even number greater that 4 that is not the sum
of two primes (ignoring 1 and 2) and then stop.
Question: Would your computer program ever stop?
Answer: Nobody knows.
Question: If the program never stops can we be sure there is some way to know
this, so we can give up and don't keep wasting computer time?
Answer: No, Turing proved this is impossible.
Computers have already looked for this number, if it exists it must be
greater than a trillion or so, but checking all even numbers one by one
would take an infinite number of steps, to test it in a finite number of
steps we need a proof, but I don't have one, nobody does. From Godel's work
we know that it's possible that such a number does not exist, but a proof,
a way to show it doesn't exist in a finite number of steps, does not exist
either. If this is the case then computers will always keep tying one number
after another and will keep finding nothing and mathematicians will keep
trying to prove that there is no such number, and keep failing to do so.
>I would submit that everything we don't understand or can't
>predict is based entirely on we 1) can't measure something,
>2) can't find something, or 3) computational complexity is
>too high. Using this as a metric, I can't think of a single
>thing we don't understand that doesn't fall under one or
>more of these categories.
How about trying to understand if a photon polarized at 90 degrees will pass
through a polarizer set at 45 degrees? Measure anything you want, look
anywhere you want, compute anything you want, and it's still a crap shoot,
the odds are 50 50. According to Quantum Physics the reason we don't
understand some things is that there is nothing to understand, no reason,
no cause, it's truly random.
>James:
>You can duplicate the binary computational sequence by
>arranging and moving pebbles.
>John:
>Certainly true, and then nobody would understand pebbles.
>James
>Pebbles are irrelevant to the computational structure.
>No one needs to understand the pebbles to perform the
>computation.
You need to understand the rules that govern how the pebbles behave, how they
move and under what conditions. Otherwise you couldn't know what pattern they
will be in next.
>You could be using bananas and the results would be the same.
Yes, then nobody would understand bananas.
>You could build an entire computer as a set of equations
I agree.
>and predict every outcome from the computer for every set of
>conditions.
I don't agree. Turing proved in 1935 that a computer program can not predict
it's own behavior and neither can we. He proved that there are some numbers
no computer can ever deal with. He proved that if the Halting problem could
be solved then that would lead to a paradox, so the halting problem can not
have a solution. This is how he did it.
First make a list of all possible binary computer programs (Pn). Yes I know,
there are an infinite number of them. If the programs don't have an endless
loop in them they will eventually spit out a digital output, we will treat
this output as a number so that program Pn produces the binary number
bn1 bn2 bn3 ... Sometimes the output will be infinitely long, like Pi,
that's OK, write it all down. Yes, this is going to be a very big list.
Sometimes the program will have no output at all because it's caught in an
endless loop, in that case just put a blank line in the list. This is the
list, well part of it anyway, the entire list is a little on the long side.
Program P1 outputs bits b11 b12 b13 b14 b15 etc
Program P2 outputs bits b21 b22 b23 b24 b25 etc
Program P3 outputs bits b31 b32 b33 b34 b35 etc
Program P4 outputs bits d41 d42 d43 d44 d45 etc
Program P5 outputs bits
Program P6 outputs bits b61 b62 b63 b64 b65 etc
etc
Now we can come up with our non computable number. We use Cantor's diagonal
method and the "not" (~) operator. The following number is non computable.
~b11 ~b22 ~b33 ~b44 ... Program P1 will not produce bit ~b11 , program P2
will not produce bit ~b22 , Program P3 will not produce bit ~b33 etc. No
computer program will ever produce this number, not even in an infinite
amount of time.
At this point you should be starting to smell a paradox. What I've said looks
pretty mechanical, so why couldn't a computer program produce it? To find the
n'th bit of our non computable number all you need to do is run the Pn
computer program until it produces the n'th bit and then "not" it. At this
point we have a computer program producing a number that no computer program
can produce. Something is not right.
The only solution to the paradox is that in general the Halting Problem must
not have a solution. This means you can't know for sure if the program will
ever produce the n'th bit. It might go into an endless loop, it might not.
It might produce the n'th bit in 5 seconds, it might produce it in 5 billion
years, it might never produce it. There is no general algorithm to decide.
Thus there are some numbers that an apparently deterministic process like
mathematics or a computer program can never find. More to the point in
question, we can not predict what a computer program will do, if we want to
know we'll just have to run it and see.
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBMrdTfX03wfSpid95AQGfWQTwwVqGVZ4U5gqMQpsPD0KVDilaKbZDJCzD
pGby9lBjECRrnsuA+sW2PBY01LXdNHwgSUxAzjyW7gshfu4qtonT1y8uTKjhvnAX
clKSTfYml3v3ML2aMyAzzFTw+p2CSaHTsgyJEbHUWoYXxNMXZdB5N+mkrQJVgTtq
mb0PHFXY2TJs6ru+TMPtTAR1kVkNPvfH+7p8UE1ab4aKNFG3a+o=
=vt/x
-----END PGP SIGNATURE-----