From: James Rogers (jamesr@best.com)
Date: Wed Dec 18 1996 - 13:57:48 MST
> >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.
*Now* I understand what you are talking about. You are correct, but in the
sense that any theorem derived from a false premise is. The computer is a
tool designed to do deterministic computation. If you are foolhardy enough
to try to do a non-deterministic computation on a computer, you do so at
your own risk.
In fact, I would submit that computers are *consciously designed* in such a
way as to be unable to solve non-deterministic problems (or more correctly,
we don't know of a way to design them so they can). So in this sense, every
outcome is *still* predictable, even for non-deterministic processes. Every
determinstic process has a predictable outcome, and every non-deterministic
process has a predictable outcome( or more precisely, a universal lack of
outcome at all).
I still maintain that we understand arithmetic computation. Not being able
to solve a non-deterministic problem is by no means contrary to this.
>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.
This is fine. If it is a deterministic process, a result will be found in a
predictable fashion assuming the computational complexity isn't too great.
If it is a non-deterministic process, then we can predict that there will
never be an outcome. The real limitation is really in there ability to
prove whether or not a process is deterministic. If a process is
non-deterministic, then a computer is the wrong tool.
> >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.
This a measurement issue. Its a crap shoot because we can't measure the
exact state of the photon just prior to it entering the polarizer. We can
only measure the outcome.
> >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.
If the rules are defined, then we understand the computation. We aren't
trying to understand pebbles.
> >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.
Again, the issue of determinism versus non-determinism. In this case, we
have infinite recursion. Doesn't sound very deterministic to me.
>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.
This is only true for algorithms that we don't know to be deterministic.
The atomic computations are always deterministic, but the algorithms don't
have to be. The software I write is always deterministic (unless I screw
up) and I always can predict the outcome. Computers are designed
specifically for deterministic algorithms, and only *really poor* software
engineers are writing non-deterministic software.
-James Rogers
jamesr@best.com
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:54 MST