create account | help/FAQ | contact | links | search | IRC | site news
 Everything Diaries Technology Science Culture Politics Media News Internet Op-Ed Fiction Meta MLP

 Relativity, Uncertainty, Incompleteness and Undecidability By chato in ScienceWed Aug 31, 2005 at 08:45:49 PM EST Tags: Science (all tags) In this article four fundamental principles are presented: relativity, uncertainty, incompleteness and undecidability. They were studied by, respectively, Albert Einstein, Werner Heisenberg, Kurt Gödel and Alan Turing. This is a very simple explanation without the technical details, but which tries to show at least the general idea behind each principle.

Relativity

Relativity says that there is no privileged, "objective" viewpoint for certain observations. Let's imagine that two ships are in the sea in a very dark night, and that each of them only has a positioning light at the tip of the mast. The night is so dark that neither points at the horizon nor the waves in the water can be seen to check on which direction each ship is moving. Under these conditions, any of the captains could say that his ship is the one that is "still", while the other ship is moving, or vice versa.

Similarly, for hundreds of years we have known that the earth is not "still" in the universe, but revolves around the sun. But, at what speed does the sun move? We need a reference view point to measure speed. We can measure the speed of the sun related to a distant object, like another star, the center of the Milky Way, the center of our star cluster, but there is nothing we could call "the absolute speed of the sun". Surely, we could measure the speed of the sun relative to the space surrounding it, which is not exactly empty but has some particles, but those particles are also moving. Any attempt to determine an absolute speed is useless, as there is always an alternative view point that is equally valid and that produces a speed that is completely different. Speed is relative.

Now, if things move relative to each other, then obviously their positions at a given time are also measured relative to each other. The universe, as we know it, has no "center" with special characteristics, and even if it had it, clearly it would be completely arbitrary to say that something is "up", "down", "to the left" or "to the right". In space, these things have no meaning. Position and direction are relative. Any measurement of them requires a frame of reference.

So far, so good, but things get a bit more complicated. Let's think for a moment, how do we measure time? We measure it with changes of position and speed: the time a certain thing takes to fall to the ground, the time a ray of light takes to move between two points, etc. A direct consequence of the fact that position and speed are relative, is that time is also relative. There is no "now" that is simultaneous to the whole universe. There is no big clock ticking for the entire universe at the same time. The following experiment has been repeatedly made: if we synchronize two very precise clocks, and then we move them, for instance, by taking one of them in a plane and making a trip around the world, while the other remains in the ground, when they are together again we can see that one of the clocks has measured a longer time than the other. If we let more time pass and we increase the speed, we obtain the typical image of an astronaut on a space trip that takes a few years for him, but that returns to earth and notices that hundreds of years have passed. While relativity of motion itself is a very old concept, Albert Einstein first showed that even time is not absolute.

Do not confuse this with subjectivity: in a movie I once heard a dialog like "for Einstein, everything was relative, for instance, half an hour with a person you love or half an hour waiting for the metro are not the same". This is not relativity, it is called subjectivity and it's a different story. Relativity says that, even with the most precise instruments, there are no "absolute" measurements, and different view points can produce measurements that are "objectively" different. This does not mean there is no objective truth, but rather that there are no privileged view points.

Uncertainty

Baseball could be played with a smaller ball, the size of a ping-pong ball, or with a larger ball, the size of a volley ball; it would look weird but the game would still be playable. The rules of the game at our scale, are the same for a small, medium or large ball. We could even figure out how to play a table version of a mini-baseball with small balls of 1 millimeter of diameter. The dynamics of the game would be the same: the ball is thrown, the ball describes a curve, the ball is hit.

However, on the scale of the very small, if we continue reducing the size of the ball until it is the size of an atom or the size of an electron, the scenario is radically changed. At atomic scale, all sort of things that would look very weird at our scale happen. An example of how different things are, when we see them at atomic scale, is the following: if we have in our living room a lamp with a control to make the light brighter or darker, we can fine-tune how much light there is in the room. If the lamp has a certain luminosity, we have the impression that we can always lower a bit the luminosity without turning off the lamp completely. This is just an illusion, because if we look closely and take a very precise source of light, then we could see that there is a point in which if we lower a little more the light, we switch it off; there is a limit under which there are no more intermediary intensity levels. Light has a minimal unit, indivisible, it is called a "photon". All subatomic particles have an indivisible unit called a "quantum", and a "photon" is a quantum of light. Because of this phenomenon, the theory that tries to explain how everything works at a very small scale is called quantum mechanics.

Now, let's get back to the baseball game. Now we no longer throw a rubber and leather ball but a very small particle, let's say an electron. This electron goes on its way to a miniaturized baseball bat with which we want to hit it. We need to know where is the electron, but to see it, we need light. The only problem is that light is made of photons, and the electron is so small that a photon hitting it will move it from its trajectory. We aim a miniature lamp to the electron to see it and we receive the photons back, but once we have received the photons we have altered the trajectory of the electron. We could try to use just a single photon but that would be enough to move the electron. We can try to make this photon less capable of moving the electron, by having less momentum, but the problem is that for doing that we should have to generate light with longer waves and that would not allow us to see the electron precisely.

Werner Heisenberg showed that if we built a machine to tell us with high precision were an electron is, this machine could not also tell us the speed of the electron. If we want to measure its speed without altering it we can use a different light but then we wouldn't know where it is. At atomic scale, no instrument can tell us at the same time exactly where a particle is and exactly at what speed it is moving. Clearly, we could try to stop the electron with a wall and in that way we would know exactly where the electron is and we would know that it is still in relation to the wall, but that has no predictive value and doesn't help us in our baseball game. When measuring, we create a distortion and we are always bound by a trade-off in the measurement of certain quantities.

Sometimes a related, but not equivalent example is given: to measure the pressure of the tires of a car, we have to let some air out. So, when the indicator reads 30.000 psi, actually the pressure is 29.999 psi or less. Measure implies interacting, and interacting implies a certain alteration. At our scale, that alteration does not matters, but when we go to the very small, this alteration is a very important part of the rules.

Incompleteness

In our normal life, there are many situations that have only two states. If you have to take a train at 8 o'clock in the morning, then there are two possibilities: either you catch the train, or you miss it; if you switch a light, it will either go on or off; the accused of a trial is declared guilty or not guilty, and so on. This logic of true or false is central in mathematics. One plus one equals two? True. Two plus two equals five? False. True or false - there are no other options.

There are many natural phenomena that have intermediate states, but logic only cares about phenomena with two possibilities: true or false, black or white, zero or one, on or off, etc. This is not a weakness of logic, but rather a definition of its scope, as for instance, botanics works with plants or geology with rocks, mathematical logic works with anything that has two states.

Logic is an old discipline whose fundamental tool is deduction or logical deduction. Let A=Mary was murdered with a knife, B=John was at Mary's place at 23:00, C=Mary died at 23:01, D=John knew Mary, E=a hair from John was found in Mary's hands, F=a knife was found with Mary's blood and John's fingerprint. A and B and C and D and E and F could imply: John is guilty. If we take G=John is left-handed and the stabs are right-handed, then A and B and C and D and E and F and G could imply: John is not guilty. Several premises are composed to reach a conclusion.

This deductive, "Sherlock Holmes"-type logic, provides the rules to compose certain facts and reach certain conclusions. For instance, if for something to be true it is necessary that other two things are true, and one of the latter is false, then the former has to be false. If to get snow we need rain and low temperatures, and the weather is warm, then there will not be snow. It's logic. There are several rules in mathematical logic that build a deductive system.

If this system is complete, then anything that is true is provable. Similarly, anything false is provable false. Kurt Gödel got the intuition that traditional mathematical logic was not complete, and devoted several years to try to find one thing, a single thing that was inside the mathematics but outside the reach of logic. Gödel searched, inside the rigidness of the laws of number theory in mathematics, a valid expression that could not neither be proven to be true nor to be false.

Let's consider this expression: "this sentence is false". If "this sentence is false" is false, then it is twice false, hence true ... and if "this sentence is false" is true, then we only need to read it to see it's false. In number theory, Gödel found a way of writing a statement p that is equivalent to "p cannot be proved", using numbers and mathematical formulas, something that is possible to handle using number theory, but that can neither be proved nor disproved within this system. To do it, he had to express many ideas as numbers and weave step by step a very long proof, but he was finally able to prove that mathematical logic is incomplete, this is, that there are true things that we could never prove that are true, and false things that we could never prove that are false.

Gödel's incompleteness means that the classical mathematical logic deductive system, and actually any logical system consistent and expressive enough, is not complete, has "holes" full of expressions that are not logically true nor false.

Undecidability

Alan Turing is considered as one of the fathers of computer science. He designed a model of how a computer works that is fundamental to computer science and showed that, for instance, a pocket calculator or a sophisticated video game console work in the same way: they read some data, check a table of rules and a memory and write some data back.

In a calculator, what is read is a key stroke, the table of rules are mathematical operations, memory is the partial result and what is written back is the final result. In a video game console what is read is the controller or joystick status, the rule table are the rules of the game, the memory is the game status and what is written back are the drawings on the screen. Memory, even when it can be very large, is never infinite and the behavior of the machine is completely determined by rules that are always obeyed, so this model is known as a "finite deterministic Turing machine".

Turing wrote many programs, and he worked in deciphering codes for the Allies during the Second World War. He quickly become aware that some programs "hang" and stayed working forever without going anywhere. This happened often when there was something strange given as input. For instance, it is possible to write a program to decipher codes made of numbers that represent the coordinates where an attack will take place, but if this program is accidentally fed with letters instead of numbers, then the program fails, as it is not prepared to this type of input. Even after solving the trivial problem of accepting only numbers, a new problem appears and it is that the coordinates could be inconsistent, for instance, they could represent a place that is farther to the north than the north pole, and so on. Every new problem solved can create new problems in the program.

If we want to write a "perfect" program, that never hangs, then one way is to test it to try all different inputs, but this is often impractical as there are too many combinations; besides this, there is a deeper problem and that's that even if a long time has passed, we can never know for certain if the program is still doing something useful or if it has "hung". Turing thought that this problem could be solved with the help of another program, and he tried to write a "superprogram" that would be able of examining another program and check if it was correct, in the sense that it would terminate at some point, instead of running forever. After several attempts, he started to suspect that it might be impossible to write such a superprogram, and finally he was able to prove that in general it is not possible to check if a program will halt.

Turing's halting problem is one of the problems that fall in to the category of undecidable problems. It says that it is not possible to write a program to decide if other program is correctly written, in the sense that it will never hang. This creates a limit to the verification of all programs, as all the attempts of building actual computers, usable in practice and different from Turing machines have been proved to be equivalent in power and limitations to the basic Turing machine. It is impossible to know if a program will "hang" under some circumstance, and modern programming techniques try to minimize the probability of this occurring, as well as ensuring a smooth recovery and avoiding data loss, but for non-trivial programs, there are usually no guarantees of correctness.

A "Blind Spot"?

These fundamental principles should not be taken as limitations to science, and they do not exclude the existence of an objective reality. They are rather limitations to some operations, such as making a measurement or working with formal logic, that have to be taken into account to understand natural phenomena.

There is a certain relationship between these principles. Both relativity and uncertainty arise from physics and are related to observations, while incompleteness and undecidability arise from mathematics and are related to the limitations of formalisms. Uncertainty and undecidability govern our capacity of making predictions, while relativity and incompleteness are related to the fact that references are necessary, but prevent us from doing certain operations. I would not like to try to take these relationships too far, instead, I would like to state another analogy.

The retinal nerves of a mammal's eye converge at a single spot, the optic nerve, which transmits impulses to the brain. This design has a disadvantage and that is that right in the point where the nerves meet, there is no sensitivity to light. This produces a "blind spot", a zone of the visual field where we cannot see. At the same time, it is curious that we usually cannot see that we cannot see. First, the blind spot is rather small; second, the brain compensates the image so we don't see a black disc floating in the air, and third, we have two eyes and their blind spots do not fall in the same visual area. We could use the fact that we know about the blind spot in the design of certain things, such as in the design of the instruments board of an aircraft, but besides that in daily life and for 99.9% of the population the existence of a blind spot has little practical implications.

Something similar happens with the laws we have discussed here. They certainly restrict observations and formalisms, but they do not mean we cannot make observations or formalizations. Even with relativity, if we are caught driving at 80 miles per hour in a 65 miles per hour zone, we will have to pay, even if relative to us the car was not moving, because we have agreed in a certain frame of reference. Even with uncertainty we can still play baseball as the uncertainty in the position of an object the size of a base ball is far smaller than what we can see with our naked eyes. Even when deductive systems are incomplete, incompleteness is not a problem to most mathematicians, and every year very complex and difficult proofs are shown without problems. Even with undecidability, high quality programs control high availability systems and most of the errors do not arise from arcane halting conditions, but rather from simple and avoidable programming mistakes.

The rules of the scientific game include relativity, uncertainty, incompleteness and undecidability. From the point of view of science, understanding these laws can lead us to new discoveries on how the universe works. Through this particular "blind spot", we can see.

Acknowledgments

Pepe Flores, computing engineer, entrepreneur, and also my professor, boss, partner and friend, in that chronological order, was the person from whom I first heard that these are the four most important laws in science. Ingmar Weber and several Kuro5hin readers also provided valuable feedback and comments.

Note: there is a spanish version of this article.

 Display: Threaded Minimal Nested Flat Flat Unthreaded Sort: Unrated, then Highest Highest Rated First Lowest Rated First Ignore Ratings Newest First Oldest First
 Relativity, Uncertainty, Incompleteness and Undecidability | 200 comments (129 topical, 71 editorial, 0 hidden)
 -1: garbage; as a budding mathematical physicist (1.00 / 25) (#4) by I Did It All For The Noogie on Tue Aug 30, 2005 at 04:41:34 AM EST

 and current Putnam fellow, I deplore this type of nonsense. I didn't read much and couldn't find your point. My guess is you read a pop-sci book, maybe Michio Kaku's Hyperspace or Green's (?) Elegant Universe, and now you fancy yourself a philosopher of science and expert on everything. Recommendation: Go to hell and fuck off. If that's unsatisfactory, put in 8-10 hard years of hard work getting a PhD in physics. BTW its a "quanta of light" for singular. I have discovered a truly elegant proof of the Generalized Colour Theorem, but alas, there are not enough bytes in the sig to write it.
 Some physicist (2.33 / 6) (#8) by kitten on Tue Aug 30, 2005 at 04:59:59 AM EST

 ""Quantum" is singular; quanta is plural. The smallest discrete amount of any quantity (plural: quanta). mirrorshades radio - darkwave, synthpop, industrial, futurepop.[ Parent ]
 lol trolled (1.15 / 13) (#9) by I Did It All For The Noogie on Tue Aug 30, 2005 at 05:00:55 AM EST

 i was hoping some moron would bite that. you biting it was too good to be true. PS I took 3 years of Latin in high school and 1 in college. OMG! I have discovered a truly elegant proof of the Generalized Colour Theorem, but alas, there are not enough bytes in the sig to write it.[ Parent ]
 Oh man you got me (1.33 / 9) (#10) by kitten on Tue Aug 30, 2005 at 05:02:51 AM EST

 yup (1.22 / 9) (#11) by I Did It All For The Noogie on Tue Aug 30, 2005 at 05:03:12 AM EST

 quip eras demonstrata I have discovered a truly elegant proof of the Generalized Colour Theorem, but alas, there are not enough bytes in the sig to write it.[ Parent ]
 Oh, quip it already (none / 0) (#108) by bml on Thu Sep 01, 2005 at 04:28:49 AM EST

 The Internet is vast, and contains many people. This is the way of things. -- Russell Dovey[ Parent ]
 ditto (none / 1) (#98) by nanometer on Wed Aug 31, 2005 at 03:01:41 PM EST

 I laughed out loud when I read that "correction" --- He who has imagination without learning has wings but no feet.[ Parent ]
 Ha, as another budding mathematical physicist (2.33 / 3) (#45) by lonelyhobo on Tue Aug 30, 2005 at 11:07:05 AM EST

 and another pompous ass, the attempt to disseminate knowledge and propagate it is not ignoble.  I didn't appreciate it either, but not everyone has read ultra-detailed stuff about this. The mathematics and thought that goes into these concepts is immensely beautiful, but it's not for everyone. [ Parent ]
 Instant "3" rating (none / 1) (#75) by PhillipW on Wed Aug 31, 2005 at 12:19:44 AM EST

 Solely for making fun of Michio Kaku. -Phil[ Parent ]
 What is this? (none / 1) (#114) by slaida1 on Thu Sep 01, 2005 at 06:38:45 AM EST

 Recommendation: Go to hell and fuck off.As a response to his article which was, as far as I can tell, written in good faith meaning no harm to anyone, you write that?What's wrong with you? I mean, how detached must one be from reality to write something so outright hateful? Are you a sociopath, some kind of Norman Bates or what? Dead momma in the attic and all that?There's something else budding in you besides mathematical physicist and it's downright destructive and hostile. Watch yourself. [ Parent ]
 Physics major (none / 0) (#117) by djp928 on Thu Sep 01, 2005 at 01:27:32 PM EST

 What's wrong with you? I mean, how detached must one be from reality to write something so outright hateful? He's a physics major. So, yeah, pretty detached. -- Dave [ Parent ]
 asshole (none / 0) (#123) by squirlhntr on Thu Sep 01, 2005 at 07:51:30 PM EST

 is what you are. go shove your Putnam and your sheepskin up your ass and retreat from the Temple of Academia, please. [ Parent ]
 this is interesting (2.88 / 9) (#6) by circletimessquare on Tue Aug 30, 2005 at 04:46:23 AM EST

 it's more philosphy than anything else: what is knowable and what is unknown just please be aware of the flaming negativity you will find here ignore it and look to the positive feedback The tigers of wrath are wiser than the horses of instruction.
 In what way (2.50 / 6) (#13) by forgotten on Tue Aug 30, 2005 at 05:40:49 AM EST

 is relativity an example of what we cannot know? --
 Right (none / 0) (#27) by chato on Tue Aug 30, 2005 at 07:15:06 AM EST

 Changed the intro paragraph, avoiding references to what can be known or what cannot be known. [ Parent ]
 No. (2.66 / 15) (#18) by benna on Tue Aug 30, 2005 at 06:00:40 AM EST

 Let's start with Einstein.  He was absolutly not saying that there could be no objective truth.  In fact, Einstein was a Platonist.  While there isn't any single reference frame which constitutes the whole truth, all of the reference frames taken togeather constitute all of reality.  The idea that reletivity says otherwise is a fantasy. Next Heisenberg.  The Copenhagen interpretation of Quantum Mechanics does support your view somewhat, but this is by no means the only view.  Some (such as myself) view quantum information as purely statistical in nature, and therefore it has no implications regarding the objectivity of the universe itself.  Uncertainty is uncertainty in measurement, not in reality.  In fact, if one believe the multiple universe interpretation of QM, the very same reasoning that applies to reletivity applies here. Ah, Gödel.  Another staunch platonist.  In fact, he was a good friend of Einstein for this reason.  Gödel did not see his imcompeteness theorem as a limitation on numbers, but as a limitation on formalism.  He was completly confident that the numbers were complete, in the platonic realm, just not the formal system. Turing's undecidablity is again a failure of logic and not a failure of empirical science.  Science would check all the inputs, and form a consenous, not look for a proof.  Proofs are in the realm of logic.  I think this is fundementally your problem.  You confuse formal logic with science. All that said I only skimmed your article, so perhaps I am completly wrong about what you meant to say. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein
 Thank you for your comments (none / 0) (#28) by chato on Tue Aug 30, 2005 at 07:16:10 AM EST

 I modified the article to try to make things clearer and more correct, using your suggestions. [ Parent ]
 wrong on undecidability (none / 1) (#48) by RelliK on Tue Aug 30, 2005 at 11:50:40 AM EST

 Turing's undecidablity is again a failure of logic and not a failure of empirical science. Science would check all the inputs, and form a consenous, not look for a proof. Proofs are in the realm of logic. I think this is fundementally your problem. You confuse formal logic with science. The problem is, you cannot check all inputs. A turing machine can do 3 things: halt, crash, or go in an infinite loop. Therefore, given an arbitrarily complex turing machine and arbitrary input, you do not know if the machine will halt in a finite amount of time. That is the very reason for undecidability. --- Under capitalism man exploits man, under communism it's just the opposite.[ Parent ]
 exactly... (none / 0) (#88) by benna on Wed Aug 31, 2005 at 05:56:05 AM EST

 Just as how in empirical science theories are tested and tested but never proven.  Perhaps some new "input" would falsifiy the theory but after enough inputs a consensus is formed.  What turing wanted was a proof, and science doesn't do proofs. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Yes, but who is saying otherwise? (none / 0) (#127) by onemorechip on Fri Sep 02, 2005 at 12:27:12 AM EST

 Who stated that Turing's undecidability was about empirical failure, in the first place? I didn't find any statement like that in the article. I haven't read all of the comments, but your initial comment was responding directly to the article rather than another comment. I smell a straw man, though I don't sense its purpose. When grandparent said you can't check all inputs, it was in response to your saying Science would check all the inputs, and form a consenous. In fact, as you acknowledge in parent comment, science would not check all the inputs. Instead, it would observe enough inputs to demonstrate whether hypothesis A is or is not a better predictor of the results than hypothesis B for some range of inputs. And science would be perfectly happy once this was done, until hypothesis C comes along, or until the range of inputs it is interested in is expanded. One other note: I don't think the theorems of Turing or Goedel point to any "failure of logic", anymore than I consider my car's inability to go 200 MPH a failure of the car. "Limitation" is a better word. What they discovered were limitations of logic. To me, "failure of logic" would be represented by a valid formal proof that X is true, accompanied by a valid formal proof that X is false, using the same set of axioms -- what logicians call "inconsistency". -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 My wording was clumsy (none / 0) (#137) by benna on Fri Sep 02, 2005 at 05:25:17 AM EST

 The article was initially titled "Science's blind spot," and I was commenting on the fact that I thought Turing wasn't so much talking about science as logic. When I said science would check all the inputs I was thinking more theoretically.  Science is empirical, and so it operates by experimentation over deduction (though it uses both).  In reality, science can't check all inputs, so it checks alot of them and eventually forms a consensus.  I should have been more clear. When I saw failure of logic I really mean limitation. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Thanks for the clarification (none / 0) (#147) by onemorechip on Fri Sep 02, 2005 at 04:18:21 PM EST

 I never saw the article in its original form. If it said that about science then your objection is justified. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 +1, Author has ability to use paragraphs correctly (1.44 / 9) (#37) by Egil Skallagrimson on Tue Aug 30, 2005 at 09:02:54 AM EST

 ---------------- Enterobacteria phage T2 is a virulent bacteriophage of the T4-like viruses genus, in the family Myoviridae. It infects E. coli and is the best known of the T-even phages. Its virion contains linear double-stranded DNA, terminally redundant and circularly permuted.
 Yessir, we've really lowered the bar. (3.00 / 2) (#51) by Pooping in Urinals on Tue Aug 30, 2005 at 12:13:23 PM EST

 "...[T]he first midget amputee getting bukkaked by 20 japanese buddhist monks and I bet your gonna say 'well thats what the miscellaneous column is for.'" -- army of phred [ Parent ]
 There was a bar? (none / 0) (#54) by Egil Skallagrimson on Tue Aug 30, 2005 at 01:30:10 PM EST

 Just how low is this bar in question? I think that somehow I can make this work in my favor.... ---------------- Enterobacteria phage T2 is a virulent bacteriophage of the T4-like viruses genus, in the family Myoviridae. It infects E. coli and is the best known of the T-even phages. Its virion contains linear double-stranded DNA, terminally redundant and circularly permuted. [ Parent ]
 You're too modest! (none / 0) (#55) by Pooping in Urinals on Tue Aug 30, 2005 at 02:00:07 PM EST

 I believe you already have. "...[T]he first midget amputee getting bukkaked by 20 japanese buddhist monks and I bet your gonna say 'well thats what the miscellaneous column is for.'" -- army of phred [ Parent ]
 C'mon, buddy (none / 0) (#57) by Egil Skallagrimson on Tue Aug 30, 2005 at 02:20:09 PM EST

 I'm the only thing holding this sinking ship together and we all know it. ---------------- Enterobacteria phage T2 is a virulent bacteriophage of the T4-like viruses genus, in the family Myoviridae. It infects E. coli and is the best known of the T-even phages. Its virion contains linear double-stranded DNA, terminally redundant and circularly permuted. [ Parent ]
 But... (1.26 / 15) (#56) by Big Sexxy Joe on Tue Aug 30, 2005 at 02:02:24 PM EST

 These limitations only apply to ordinary humans.  The transhumans of the future will face none of these limitations. I'm like Jesus, only better. Democracy Now! - your daily, uncensored, corporate-free grassroots news hour
 You are wrong (1.14 / 7) (#62) by maxsilver on Tue Aug 30, 2005 at 05:38:15 PM EST

 If two clocks are moved in different reference times, they maintain the same time. Okay, before you burn me, listen to the proof. For you to move a clock into an area and at a speed that consists of a different spatial reference, and that would have a different physical effect on the mechanics of the clock, you have got to perform an euqivalent energy transformation on this clock to get it into this position. So in the second frame of relative reference, the clock is going quicker, but because energy transference is not instantaneous, there is no way you can compare the clocks. When you do manage to bring back the second clock into the original frame of reference, you are going to reverse the energy effect on the clock - if it waent faster, the journey back will make it slower, and vice versa. Don't get me wrong, you are not moving back in time, rather, which the original reference has maintained its relative speed, the other one has changed. So the other clock is ticking faster, and by the time they land at the same spot, they are the same time once again. Of course the is the matter degradatory effect of this travel on whatever material you transport, so this experiment can never produce accurate results if actually performed.
 Your criticism... (none / 1) (#64) by joto on Tue Aug 30, 2005 at 06:06:17 PM EST

 ...contradicts both established physics theory, and observations from experiments that have actually been done. I would recommend you to learn more about the subject. [ Parent ]
 Your opinion (1.00 / 2) (#67) by maxsilver on Tue Aug 30, 2005 at 06:46:35 PM EST

 Is a paraphrase of 3rd rate 70 years old mathematical and physical formula. I would suggest you start examining recent papers on this topic, and be one of the few actually aware of the great change that is currently being discussed in proper circles. Oh wait, let me guess - you get your scientific theories from the New Yorker. I think you should re-examine which of the Einstein theories are regarded as "established", and which not. [ Parent ]
 Which papers? (none / 0) (#69) by parrillada on Tue Aug 30, 2005 at 07:11:35 PM EST

 I would suggest you start examining recent papers on this topic Which papers? I am not aware of any in the last 20 years. Mendel Sachs was wrote on this topic in the 70s but as far as I can tell he didn't manage to convince many mainstream scientists. Also, the 'proof' you provided in your prior post was very convoluted and I could hardly understand it. I would be interested in understanding what you are saying, however, if you wish to re-write it so that it is coherent. [ Parent ]
 Go to the university (1.00 / 2) (#87) by maxsilver on Wed Aug 31, 2005 at 05:36:15 AM EST

 At the Humbold university library there are 100s of papers on this topic in the library, from various researchers. There is also a lot of discussion. These are not papers that get published in Nature or any other large scale magazine, these are just the usual papers that accumulate when lots of people are dissatisfied with a theory, because the data is not backing it up. After a while, a sudden breakthrough comes, and it appears as if one man discovered everything. The academic enviroment is a bit different from its potrayal. [ Parent ]
 Way to go... (3.00 / 3) (#96) by joto on Wed Aug 31, 2005 at 12:26:54 PM EST

 So these sacred holy papers, that you won't name, and that you won't tell the authors of, nor which journal they were published in, can only be found at, what? At Humbold university library? You mean, I can't just download them, get them from any other university library, or order them through, the net? I really have to go to Humbold? And since the papers only exist at Humbold, nobody can criticize them either, because they don't have names, so nobody can know which paper the critiscism refers to. Very practical, I must say! Furthermore, these papers, which only exist at Humbold, are what constitutes "established" physics. I mean, who have ever heard of that dude Einstein? He's been dead for over 50 years! I marvel at your intellect, and the fact that you have a library card. But if I had to choose, yes, I would rather have my physics from the New Yorker, than from Humbold. I'm just not that interested. [ Parent ]
 Drop some names if you like, but otherwise (none / 0) (#102) by parrillada on Wed Aug 31, 2005 at 04:09:22 PM EST

 ...I will not take you seriously. I have researched this topic at a much larger university than Humbold, and I have not found 100s of papers in reputable journals or science magazines. I have found, maybe 20 at most, though only two or three authors were responsible for all of that correspondence. [ Parent ]
 Incorrect (none / 0) (#110) by GhostfacedFiddlah on Thu Sep 01, 2005 at 05:22:23 AM EST

 If a clock moves at C (speed of light) away from me for X seconds, and then at C towards me, I will experience 2X seconds before it reappears before me, and it will not have moved at all.  I'm not sure exactly why this is, but the mathematical explanation is in the fact that it's the clock - not me - doing the accelerating. [ Parent ]
 Twin paradox (better explanation here) (none / 1) (#111) by GhostfacedFiddlah on Thu Sep 01, 2005 at 05:34:31 AM EST

 Reality disagrees with you (none / 0) (#158) by MrMikey on Sat Sep 03, 2005 at 05:03:22 AM EST

 If you had the spare cash, you could pick up a couple of HP atomic clocks, leave one at home, fly the other one around the world, and come home to find that the two clocks now disagreed. This experiment, and others like it, have been done many times, and the results agree with the calculations done based on Special Relativity. [ Parent ]
 No need to do it yourself (none / 0) (#165) by chato on Mon Sep 05, 2005 at 03:44:48 AM EST

 VOTE THIS ARTICLE DOWN (1.13 / 15) (#83) by Sigismund of Luxemburg on Wed Aug 31, 2005 at 03:51:44 AM EST

 The author has been modding helpful editorial comments down in his own story! ANONYMISED
 Sorry (2.50 / 2) (#86) by chato on Wed Aug 31, 2005 at 05:23:41 AM EST

 I modded that down because I considered the tone of the comment unhelpful (it was not ethnicity of course, just a mistake on my part), but you can see that I actually did what the commenter asked. Sorry for the mistake. [ Parent ]
 -1, article promotes fear, uncertainty and doubt (1.08 / 12) (#85) by United Fools on Wed Aug 31, 2005 at 05:17:26 AM EST

 We need certainty and dependability. This article makes our head spin and confuses us. we have too much in this world to fear already; look at the news today, everything is negative. We don't need more. We are united, we are fools, and we are America!
 Errors of Understanding (2.85 / 7) (#91) by Morosoph on Wed Aug 31, 2005 at 10:18:04 AM EST

 Relativity Similarly, for hundreds of years we have known that the earth is not "still" in the universe, but revolves around the sun. But, at what speed does the sun move? We need a reference view point to measure speed. In an accelerating frame of reference, such as where the earth is travelling around the sun, you need to invoke general relativity, where acceleration and gravity are comparable. Because of the different densities of the earth an the sun, you can tell the difference; the centre of rotation is nearer the sun, for a start. Gravity and acceleration gives otherwise indistinguishable objects a frame of referrence, or else gyroscopes simply wouldn't work. Special relativity holds for inertial frames; the above example isn't such a frame of reference. Uncertainty Now, let's get back to the baseball game. Now we no longer throw a rubber and leather ball but a very small particle, let's say an electron. This electron goes on its way to a miniaturized baseball bat with which we want to hit it. We need to know where is the electron, but to see it, we need light. The only problem is that light is made of photons, and the electron is so small that a photon hitting it will move it from its trajectory. We aim a miniature lamp to the electron to see it and we receive the photons back, but once we have received the photons we have altered the trajectory of the electron. We could try to use just a single photon but that would be enough to move the electron. We can try to make this photon less capable of moving the electron, by having less momentum, but the problem is that for doing that we should have to generate light with longer waves and that would not allow us to see the electron precisely. The Heisenberg's uncertainty principle goes deeper than this. It's not just about measurablity, it's about the nature of reality itself. The particle itself has an indeterminate position or velocity (or equivalently energy/time, amoungst other pairings). Incompleteness Let's consider this expression: "this sentence is false". If "this sentence is false" is false, then it is twice false, hence true ... and if "this sentence is false" is true, then we only need to read it to see it's false. In number theory, Gödel found a way of writing a statement p that is equivalent to "p cannot be proved", using numbers and mathematical formulas, something that is possible to handle using number theory, but that can neither be proved nor disproved within this system. To do it, he had to express many ideas as numbers and weave step by step a very long proof, but he was finally able to prove that mathematical logic is incomplete, this is, that there are true things that we could never prove that are true, and false things that we could never prove that are false. This is a misunderstanding of what the incompleteness theorem says. "This statement is false" is simply not well-defined. Incompleteness isn't about apparent paradoxes; rather, it means that if I wish to state a theorem, such as "the Continuum hypothesis holds true"; some of the theorems that I would wish to state could not be shown to be either true or false. If I extend my set of axioms to resolve the issue, there would be other unresolvable theorems. Undecidability Turing's halting problem is one of the problems that fall in to the category of undecidable problems. It says that it is not possible to write a program to decide if other program is correctly written, in the sense that it will never hang. This creates a limit to the verification of all programs, as all the attempts of building actual computers, usable in practice and different from Turing machines have been proved to be equivalent in power and limitations to the basic Turing machine. It is impossible to know if a program will "hang" under some circumstance, and modern programming techniques try to minimize the probability of this occurring, as well as ensuring a smooth recovery and avoiding data loss, but for non-trivial programs, there are usually no guarantees of correctness. It is possible to prove some programs, and also to write software that will provably halt, or where the range of inputs over which it will not halt is known. It is simply not possible to do this for all cases. In particular, if I come to you with a program, there is no algorithmic method by which you could determine its halting status.
 Re: errors of understanding (none / 1) (#92) by chato on Wed Aug 31, 2005 at 10:55:46 AM EST

 Relativity: With sun and earth I am just trying to give a simple example anyone can understand about why a frame of reference is necessary to measure speed. However, you are right and I might have sacrificed more detail than was necessary. Uncertainty: I think understanding the impossibility of measuring is a first step towards understanding that an atomic particle has indeed an indeterminate position or speed which provides the probability of obtaining certain measurements. However for a person that hasn't studied quantum physics, the problem of measuring and predicting can be easier to grasp as a first approach. Incompleteness: I give "this statement is false" just as an example of a paradox involving a self-reference. Later I say that Godel's used a statement p that was "p cannot be proved", which is not the same as in the example. Undecidability: I say in the previous paragraph that in general it is not possible to check if a program will halt. A trivial turing machine that under any input halts immediatly can be certainly checked by another machine (and there are other examples) but a machine to decide a general program cannot be built. [ Parent ]
 Cool... (none / 0) (#139) by Morosoph on Fri Sep 02, 2005 at 05:42:32 AM EST

 You have to throw in some boundary cases to make some interesting discussion :o) [ Parent ]
 I agree with most of what you say but... (none / 1) (#101) by benna on Wed Aug 31, 2005 at 03:53:20 PM EST

 Gödel actually does have to do with paradoxes.  He uses the paradox "This statement cannot be proved within this system of formal logic" to create a wff in his formal logical system, transalating it into Gödel Numbers.  It could be shown using the Gödel numbers that the wff is true, but for that very reason the wff could not be proved within the formal logical system. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 That's not a paradox (none / 1) (#126) by onemorechip on Thu Sep 01, 2005 at 11:28:18 PM EST

 IANAM, but I'm thinking it's not a paradox for the following reason. Goedel didn't show that a particular statement p is true and unprovable. He proves that there exists some statement p such that p is both true and unprovable. If you can't actually determine what p is, and also prove that about p, you don't have a paradox. Goedel proves a statement about number theory (and other axiomatics systems) but that statement is not the unprovable statement p. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 Umm (none / 0) (#136) by benna on Fri Sep 02, 2005 at 05:19:54 AM EST

 I might be misunderstanding you, but I think you are wrong.  In Godel's proof P = "P is not provable."  P is self referencing but it does exist.  The important part is not that one can construct the statement "P is not provable," but that "P is not provable" IS P. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Bear with me... (none / 0) (#146) by onemorechip on Fri Sep 02, 2005 at 04:15:21 PM EST

 In Godel's proof P = "P is not provable." P is self referencing but it does exist. The important part is not that one can construct the statement "P is not provable," but that "P is not provable" IS P. But p is not a theorem that is provable in the given formal system. If it were, then (obviously) the system would not be consistent. If we managed to construct p for system S, then we could never prove that we have found p by applying the axioms of S. p's self-reference is to its own provability; it makes no assertion about its own truth value. There is no paradox in proving that "p exists, such that p states its own unprovability, p is true, and p is unprovable", because that statement is definitely not the same as p. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 Fine (none / 0) (#152) by benna on Fri Sep 02, 2005 at 07:44:57 PM EST

 I'm using the word paradox a bit too loosely. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 On the other hand (none / 0) (#157) by onemorechip on Fri Sep 02, 2005 at 09:47:15 PM EST

 I just looked up paradox in Wikipedia and this would be a veridical paradox, the first of Quine's 3 categories. Guess I'm just accustomed to using the word to mean "antinomy", Quine's third category. Examples: Russell's paradox, Curry's paradox (both linked from that article). -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 No paradoxes here... (none / 0) (#148) by SageGaspar on Fri Sep 02, 2005 at 06:03:53 PM EST

 Let's call the sufficiently-rich axiomatic system A. The statement is that "P is not provable within the confines of axiomatic system A."There is no paradox. The point is to demonstrate that A is not complete -- there are statements that can be formulated within A but are not provable within A.I can certainly add "P is not provable within the confines of axiomatic system A" as an axiom to create axiomatic system B. Our original statement is now true in axiomatic system B. This is not a paradox. And, in turn, Godel assures us that there is a statement, Q, equivalent to "Q is not provable within the confines of axiomatic system B" that can be formulated within B.The only paradox would be if I could either (1) prove P true within the confines of A or (2) prove P false within any axiomatic system that contains A. [ Parent ]
 accelleration and general relativity (none / 1) (#120) by Norwegian Blue on Thu Sep 01, 2005 at 06:46:28 PM EST

 It's been a while since I studied this... (none / 1) (#125) by onemorechip on Thu Sep 01, 2005 at 11:02:16 PM EST

 So where does special relativity stop? With accelerated timeframes, because the math gets harder? Or where you get contradictory results? I may be off base since I haven't studied physics in many years, but I'll try to answer that the best way I can. As long as space-time is Euclidean (flat), you can apply special relativity even if there is acceleration -- even variable acceleration, as in the twins paradox. The problem with gravitational fields is that they are not flat, they are spherical (well, assuming spherically symmetric distribution of mass). The simple Lorentz transformations can't handle curvature, so general relativity uses a different mathematical tool -- tensor analysis. But even in a curved gravitational field, if you look at local phenomena (confined to a small enough volume that the curvature is unnoticeable), special relativity can be applied to get accurate results -- just as surveyors or cartographers can get by with Euclidean geometry as long as they are only concerned with a small part of the Earth's surface. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 infinitesimal approximations are not the point (none / 1) (#132) by Norwegian Blue on Fri Sep 02, 2005 at 04:44:09 AM EST

 I didn't realize I sounded so clueless that I was the one in need of an answer :) You might consider my parent post as a reply to your post. You describe how things are taught, special relativity treats inertial frames and general relativity treats general  coordinate systems. But you could also consider tensor math without mass as 'beefed up special relativity'. A bit bulky for most purposes, people would usually find a way to do without. If Einstein would have introduced that one, I doubt if it would have made a big bang. As you mention, often you can just keep working with inertial frames on an infinitesimal base. Accelerated timeframes do not cause inconsistencies in special relativity, but with gravitation, it's no longer a matter of adding a new math technique, you need a different model. SR is not just an approximation, in some cases it's plain wrong. You have to make mass part of the equation, and no longer consider gravitation as a force. And this is a major shift. Now tensor math becomes essential. Of course, there's a catch to the choice. You don't really have to choose between the two ways of separating SR and GR, it's just a matter of being aware that there's two possible ways and understand the reasons for each. The problems I mentioned about a charge in an accelerated frame of reference are macroscopic BTW. You get 'radiation behind the horizon' effects. [ Parent ]
 I'm not sure I follow you (none / 0) (#145) by onemorechip on Fri Sep 02, 2005 at 03:58:38 PM EST

 SR is not just an approximation, in some cases it's plain wrong. Without introducing non-uniform gravitational fields, can you identify such a case? You have to make mass part of the equation, and no longer consider gravitation as a force. And this is a major shift. Now tensor math becomes essential. I think that's what I was saying. But the reason mass matters is that the resulting gravitational field is non-uniform and this causes curvature. The problems I mentioned about a charge in an accelerated frame of reference are macroscopic BTW. You get 'radiation behind the horizon' effects. I think special relativity can handle those things. Aren't Maxwell's equations Lorentz-invariant? I recall that the Lorentz transformations preceded special relativity by years or maybe decades but Einstein showed that these transformations are implied by the invariance of the speed of light -- that's SR. Couple Lorentz invariance with the principle of equivalence and you can predict many of the things GR predicts, such as the slowing of clocks in a gravitational well. Other effects such as orbits of planets and bending of light require GR to model accurately because they aren't local. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 Ways to understand (none / 0) (#162) by Norwegian Blue on Sun Sep 04, 2005 at 06:48:19 AM EST

 another way to put it (none / 0) (#163) by Norwegian Blue on Sun Sep 04, 2005 at 02:28:47 PM EST

 Keeping the (existing) equivalence principle(s) ment dumping gravity as a force from SR - not just Newton's form. It's possible that Einstein made up his mind about that before he published SR. [ Parent ]
 OK, I think I follow you (none / 0) (#199) by onemorechip on Fri Sep 16, 2005 at 12:35:54 AM EST

 Sorry, my mistake - and my rudeness. I should have said(and taken the time to make sure) I'm not disagreeing with anything you say about relativity. It's just that if you use GR to explain shortcomings of SR, you're using hindsight from GR, which I'm trying to avoid for several reasons. Afterwards, everything is consistent and you use the old model as an approximation. You're explaining how it works(and correctly, I think), while I'm talking about where a theory breaks down. The only thing I took issue with is the statement that SR is broken. A mathematical model of the physical world can only apply within certain constraints. For SR the constraint is that space must be flat, Euclidean. And if you get far enough from any massive object (intergalactic space, say) I suspect you will find space to be flat enough that SR could apply over distances of many light-years. I see what you are saying, that if we intentionally avoid curved space by choosing a spot far from gravitational influences, we are doing so with hindsight. It doesn't mean the hindsight is incorrect. I don't fully understand GR mathematically because I never went that far in physics, choosing an engineering curriculum instead. So bear with me if I don't follow all of your discourse, or if I have some misconception. It is my thinking that even if SR only applies locally, you could apply it in a curved space-time by breaking space-time into very small regions and treating it as a finite-element analysis. For instance, to model the curving of a beam of light in a gravitational field, you could calculate the path of the beam through each element using SR plus equivalence plus EM; this gives you the point of entry and exit for each element. Orbital precession could get a similar treatment. In the limiting case, would this predict the same path that GR predicts? I myself don't know, but I'm guessing it would, because I'm not aware that Einstein based GR on any experimental evidence that would contradict this approach. Perhaps he took a similar approach, and derived his tensor equation as the limit. Also, that SR had no covariant version for general coordinate systems was not alarming(although I'm not entirely sure here, I'd like confirmation), covariance problems with gravity spelled instant disaster. Not because of 'approximation problems' as for example Mercury's orbit, but because gravity made no sense at all in special relativity. Note that if gravity could have been treated as any other radial force, covariance+ Newton's law of gravity would have led instantly to laws of gravito-magnetism as just another case of anyforce-magnetism. Hmmm, that's a thought I'd not been exposed to before. I wonder if that means the finite-element approach is also doomed (i.e., doesn't converge on GR). Maybe not, because it does incorporate equivalence (so gravity isn't treated as a force). Thanks for the insights. -------------------------------------------------- I did my essay on mushrooms. It's about cats.[ Parent ]
 The Turing halting problem (none / 0) (#159) by dn on Sat Sep 03, 2005 at 02:49:05 PM EST

 It is possible to prove some programs, and also to write software that will provably halt, or where the range of inputs over which it will not halt is known. It is simply not possible to do this for all cases. It isn't merely a limitation of logic or science. A Turing machine has a memory that can store infinitely many infinitely-large numbers. Turing's halting theorem is therefore more a statement about the structure of the theory of math, rather than a statement about computation. In essence, what Turing is saying is that you can write down a Boolean test procedure for a set of real numbers, yet not get an answer even in principle. This does not apply to physically-realizable systems. The halting problem is always decidable in finite time for real world computers. (Which is not terribly surprising, as one technical name for real computers is "finite state machine".)     I ♥ TOXICWASTE [ Parent ]
 Could you please provide some references? \$ (none / 0) (#174) by hummassa on Tue Sep 06, 2005 at 06:48:20 AM EST

 [ Parent ]
 Sure (none / 0) (#178) by dn on Tue Sep 06, 2005 at 08:15:22 PM EST

 First, a correction. I said "A Turing machine has a memory that can store infinitely many infinitely-large numbers." Turing machines actually store finite numbers. The Wikipedia article on Turing machines looks reasonably accurate. Turing machines and real computers have other differences, but the big one is infinite versus finite memory. You can always discover whether a program on a deterministic machine with finite memory will halt, by simply letting it run and recording the full state at each step. If it ever repeats the same state twice, then you know it will run forever. Otherwise it will halt. You may have to be very rich and patient to accomplish this, and you don't get any enlightenment about why, but it always gives you an answer with finite work and time.     I ♥ TOXICWASTE [ Parent ]
 I voted -1 (1.66 / 6) (#94) by bml on Wed Aug 31, 2005 at 11:07:51 AM EST

 I think you make serious mistakes in each of the sections: Relativity: The first part is not Einstein's relativity. Galileo started and Newton settled all that "frame of reference" thing. Then you speak about time not being absolute, because, you propose, "there are no absolutes". Well, Einstein actually found the one absolute: C (the speed of light). And it's precisely because C is invariant that time is not. Uncertainty: The problem with observability is not that the measurement disturbs the momentum/position of the particle. This is a common misconception, but the urcentainty principle applies also to theoretical "ideal" measurements (those that don't affect the particle being measured). The underlying mathematical principles are rather hard to grasp, so your explanation is an acceptable simplification. But you should really indicate that it is a simplification. Incompleteness: So wrong. You start hinting at the difference between traditional logic and fuzzy logid, but then, instead of going there, you unrelatedly mischaracterize Gödel's theorem. It has nothing to do with the "this sentence is false" thing. Not even with the "p cannot be proved" statement, which is, however, closer. The real deal is that systems (certain systems, actually) cannot be proved just with the system's own tools. You need to use things from outside the system. Your last phrase is just wrong. Undecidibility: This one is plain wrong. I can write you a one-line program that will certainly halt for all possible inputs. Where's the undecidibility here? The "halting problem" does not apply to every single algorithm. Plus, undecidability is more than just the halting problem. Something decidable is something you can always solve using an algorithm. I don't see how undecidability can be considered a general law of physics, or the universe, or whatever. In summary: I'm sorry, but you don't really seem to know these issues very well. Not well enough to write an article on them, at least. The Internet is vast, and contains many people. This is the way of things. -- Russell Dovey
 Re: I voted -1 (none / 1) (#95) by chato on Wed Aug 31, 2005 at 11:20:01 AM EST

 Relativity: I say "While relativity of motion itself is a very old concept. Albert Einstein first showed that even time is not absolute.". Uncertainty: as I said before, this explanation is a simplification. Incompleteness: you are right in regard to the last phrase, "that are not logically true nor false." should be "that are not provable true nor false" or something similar. Unfortunately, I can't edit the article right now. I'll write an errata after some more comments. Undecididibility: I already replied to your objection in "Re: errors of understanding". [ Parent ]
 Incompleteness (none / 0) (#116) by JaxWeb on Thu Sep 01, 2005 at 09:55:26 AM EST

 The incompleteness section is quite wrong. For instance, formal logic is not incomplete and it isn't inconsistant (it is quite easy to prove that). As parent mentioned there are other systems of logic such as Three State Logic or Fuzzy Logic which are also consistant, so what was said at the start is irrelevent. There are two parts of the theorem. The part we care about says that either: (a) The system is inconsistant or (b) There exist true statements which are not provable. If I recall correctly it is actually proved in a sort of "This sentence is false" type way, and then shown that if that statement is true then the compliment of it is also true, which would make the system inconsistant. But then it can be shown that the statement must actually be true (like I say, it isn't actaully "This sentence is false" though). It is really important to make sure you know logic, as a system, is consistant (but I think Godel's theorem does assume standard logic). [ Parent ]
 +1, but not because there weren't errors... (3.00 / 2) (#106) by debillitatus on Wed Aug 31, 2005 at 06:17:23 PM EST

 because there were. But it's not possible to write about these topics to the layman and not make a bunch of incorrect statements. I mean, hell, it's definitely no worse than Michio Kaku, and that bitch is in bookstores. I do agree with you that these are pretty damned important concepts, and they are grossly misunderstood by the layman. Anything on them which is not completely wrong helps, IMHO. Damn you and your daily doubles, you brigand!
 This is not right.. (1.25 / 4) (#107) by StephenThompson on Thu Sep 01, 2005 at 01:30:10 AM EST

 These descriptions are wrong. I wish this hadn't been voted up as it just perpetuates some wacky ideas. I'm not going to even try to explain whats wrong, but just say that the characterizations made here are essentially gibberish. If people want to get a grip on this stuff, go take a course on the subject; or at least read a book from a physicist or computer scientist.
 READ ME FIRST: ERRATA (3.00 / 5) (#109) by chato on Thu Sep 01, 2005 at 04:43:43 AM EST

 Several readers pointed to errors and suggested corrections after the article left the editing queue. I am keeping a page with ERRATA and an updated version with these errors corrected. Perfection does not exist :-) so if you find a mistake, please try to be specific about what do you think is still wrong after the errata and how it can be corrected. Writing and editing this article has been quite an experience, there is a lot of flamebait, and sometimes plain rudeness, but also many helpful, constructive comments from well educated people. Thanks everybody.
 Contact the editors (none / 1) (#133) by bml on Fri Sep 02, 2005 at 04:44:30 AM EST

 Your corrected version addresses everything I disagreed with, and I would have definitely voted it up. Great work. Now, your original article is in the front page of K5, meaning it's getting a lot of visibility from people with a limited understanding of the issues discussed. I suspect very few of them will find the link to the corrections. As I don't think anyone who voted it up would have any objections to the revised version, I think you should contact a K5 editor (help@kuro5hin.org - I think) and ask them to change the current text for the new one. Re-reading my original protest, I think it was unnecessarily rude and a bit unconstructive. I apologize if that is also the impression I gave you. And congratulations again on a very good article that just lacked some more time on the edit queue. The Internet is vast, and contains many people. This is the way of things. -- Russell Dovey[ Parent ]
 Theories or the concepts behind them. (2.50 / 4) (#113) by Saggi on Thu Sep 01, 2005 at 06:10:36 AM EST

 Agree - Good article (none / 0) (#193) by bsavoie on Fri Sep 09, 2005 at 06:16:46 PM EST

 I think physics is a religion, where people actually believe that they are nothing. They believe they are biological computers running on the food they ate and with inputs from their parents and teachers.With this "belief" that they ignore, they are just like fundamentalists, they know they are right. You just stepped into their unconscious and got their projections that protect that soft spot. Good work.As long as I have taken the bait, to speak out, the speed of light is changing. It is getting faster, and in another 200 or 300 years everyone will know this is true. That is explained on my website www.dyad.org. Further, in another many millions of years, the physical universe will evaporate and we will all be telepathically connected without it.I hope someone will record this, so in 1,000 years, it will help them to understand how 'objects' are just missunderstandings between 'people'. We are all God, and we only argue about who has advantage. Bill Savoie (another god just like you) May Peace and Love be your path[ Parent ]
 Light example (none / 1) (#115) by Eustace Cranch on Thu Sep 01, 2005 at 09:26:38 AM EST

 The example of turning down the dimmer switch on a light doesn't really make sense. Let's assume a fixed wavelength and measure the intensity by the average amount of energy emitted per second. This value can in theory be made arbitrarily small without switching the light off. What you perhaps mean is that the emission gets lumpy, and some seconds there will be a burst, and other seconds there will not, but that's not quite the same thing. It's also a big leap from there to quantum mechanics (nothing in the experiment really suggests this is something fundamental about light).
 Emission gets lumpy (none / 0) (#129) by chato on Fri Sep 02, 2005 at 04:33:04 AM EST

 You're right about the example. I have added this clarification to the errata page. I think the experiment suggests something fundamental: light, even if it behaves as a wave, is a special kind of wave that propagates in "quanta" (packets). The example of the dimmer was the simplest explanation of this phenomenon I could think of -there might be others. [ Parent ]
 Anal retentive mathematical logician chimes in (none / 1) (#118) by city light on Thu Sep 01, 2005 at 04:24:26 PM EST

 You say: There are many natural phenomena that have intermediate states, but logic only cares about phenomena with two possibilities: true or false, black or white, zero or one, on or off, etc. This is not a weakness of logic, but rather a definition of its scope I wouldn't limit its scope so readily - Boolean (true/false) logic plays an important role in lots of formal systems, including those used to describe and prove things about continuous phenomena, things with intermediate states. There are many different logics, not just one 'mathematical logic', and some, for example intuitionistic and multi-valued logics, allow for various kinds of uncertainty in their propositions. The logic you describe is classical propositional logic, and it is  complete! Various complete deductive systems exist for classical propositional logic. Incompleteness doesn't come into action until your formal system gains the power to model arithmetic - something like first-order predicate logic with axioms for Peano arithmetic, is required. And even then, the incompleteness arises from the attempt to describe arithmetic with a recursive set of axioms, and not from the system of logical deduction itself.
 Right (none / 0) (#130) by chato on Fri Sep 02, 2005 at 04:39:50 AM EST

 I added your indications to the errata, separating boolean logic from propositional logic and the theorems on natural number. Joining everything under a single term "mathematical logic" was an oversimplification. Thanks for your suggestions. [ Parent ]
 A few questions... (none / 0) (#141) by SageGaspar on Fri Sep 02, 2005 at 10:25:23 AM EST

 As a fourth-year undergrad in math, I am just starting to read up on some of this stuff, and I wondered if you'd be generous enough to respond to a few things, or recommend a source. 1. Godel's first incompleteness theorem says, to my understanding, "If axiomatic system A can construct the natural numbers, then a statement can be formulated within the confines of the system that is logically equivalent to 'This statement cannot be proven within axiomatic system A.'" My qualm is with the term "construct," as I'm not sure what properties the natural numbers are supposed to have. 2. On this point, it seems like you could construct them in Euclidean geometry using the idea of commensurability/proportionality, but I have heard that there is an axiomatization of said geometry that is complete. 3. As a logician, given two distinct logical axiomizations -- for example, where the law of the excluded middle is assumed/not assumed -- don't you need some sort of deeper axiomatic system to discuss their differences rigorously? Or do you just use the axioms that they have in common? I assume that most every axiomatic logic system has something equivalent to the law of non-contradiction, for example. [ Parent ]
 measurement (2.50 / 2) (#119) by squirlhntr on Thu Sep 01, 2005 at 06:09:45 PM EST

 empty posturing (none / 0) (#121) by Sacrifice on Thu Sep 01, 2005 at 07:38:11 PM EST

 There's nothing in the above post :( [ Parent ]
 yep (none / 0) (#122) by squirlhntr on Thu Sep 01, 2005 at 07:44:42 PM EST

 haha and that is the whole point. except i did mention papers to read. there's no better way to explain it, because in the end, it's not even explainable. as the saying goes "in mathematics, we don't understand things, we just get used to them." and yes, i am a mathematician IRL ;) [ Parent ]
 Hmm? (none / 1) (#134) by JaxWeb on Fri Sep 02, 2005 at 05:00:48 AM EST

 "it's not complicated. just read the original papers." Have you read Godel's paper? It is complicated. Turing's isn't really though. Neither have anything to do with the "fundamentals of the universe" however. "lots of other papers all hit on the same thing, as well: Cantor's work." I don't understand how you mean? [ Parent ]
 The grandparent is mostly nonsense but... (3.00 / 2) (#138) by benna on Fri Sep 02, 2005 at 05:27:27 AM EST

 I do think Godel's paper has metaphysical implications.  Godel was a staunch platonist, and saw his paper as the falsification of mathematical formalism. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Possibly (none / 0) (#140) by JaxWeb on Fri Sep 02, 2005 at 07:45:27 AM EST

 Hmm. Maybe so. You don't happen to know of a website with any arguements on deeper meanings (in terms of the metaphysical implications you mentioned) of his theorems do you? Not quite relatedly, have you seen this? http://en.wikipedia.org/wiki/G%C3%B6del%27s_ontological_proof (Interesting, I thought) [ Parent ]
 A good book to read is... (none / 0) (#151) by benna on Fri Sep 02, 2005 at 07:42:34 PM EST

 Incompleteness: The Proof and Paradox of Kurt Godel by Rebecca Goldstein.  It looks at Incompleteness from a philosophical perspective. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Thank you (none / 0) (#153) by JaxWeb on Fri Sep 02, 2005 at 07:48:10 PM EST

 Thank you very much, I shall buy. You don't happen to know of any formal books on the foundations of mathematics do you? I'd really like a very complete one on the topic. [ Parent ]
 Clarification (none / 0) (#142) by SageGaspar on Fri Sep 02, 2005 at 10:31:07 AM EST

 I have a very, very basic grasp on platonism, and I thought I understood formalism, but I cannot see incompleteness as refutation or support for either.I am sure this is my fault, not yours, as I am fairly ignorant about philosophy, but I am very interested in learning more. If you could recommend any sources or give a brief explanation about how incompleteness refutes formalism, I would be eternally indebted. [ Parent ]
 Read... (none / 0) (#150) by benna on Fri Sep 02, 2005 at 07:40:58 PM EST

 Incompleteness: The Proof and Paradox of Kurt Godel by Rebecca Goldstein.  It is a fairly easy read and it looks at Godel's incompleteness from a primarily philosophical perspective.   Briefly, one of the main goals of formalism was to prove the consistency of all of mathematics.  They had done this for most every field, except that it was contingent upon arithmatic being consistant, and they couldn't come up with a proof for that with a finite number of axioms.  Formalists didn't trust infinity, so it had to be finite.  Godel's second Incompleteness theorem states that any formal system sufficient for arithmatic can not prove itself consistant.  This was devistating to the formalists. Godel believed arithmatic to be consistant anyway though.  His view was that any formal system with a model which exists in the platonic world must be consistant.  He saw this as the only way to believe arithmatic to be consistant, and for that reason so it as strong evidence for platonism. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Thanks! (none / 0) (#176) by SageGaspar on Tue Sep 06, 2005 at 01:02:37 PM EST

 Thanks for the response!I will certainly take a look at it. [ Parent ]
 Nonsense (2.33 / 3) (#124) by trhurler on Thu Sep 01, 2005 at 10:37:40 PM EST

 First of all, these are four single points taken from three separate fields, and they are by far not 'the most important' things in those fields. Second, your definition of undecidability is completely wrong. Computers don't have letters. They only have numbers. A letter is simply a representation on your screen of what to the computer is in fact a number. Undecidability has nothing to do with input validation, and everything to do with the fact that some algorithms' exit conditions cannot be guaranteed to occur for given inputs unless you actually run the algorithm or another algorithm of equivalent complexity on those inputs. That said, it is not a significant problem anymore, and hasn't been for a long time, because algorithms are no longer the core problem of computing. Third, your description of Godel's work is both wrong and hyperbolic. What he actually proved is that in any system with finite axioms, there are statements which cannot be proven or disproven. It sounds a lot more impressive than it is. In reality, again, it has basically no impact on the real world whatsoever. Moreover, it is relatively trivial to simply establish an additional axiom that will enable you to work around the problem, and there is no shortage of axioms to be adopted or ways of verifying their accuracy without the use of logic(empirical data, usually) in any case that actually applies to the real world and not simply to some meaningless abstraction. Fourth, uncertainty does not mean the particle doesn't have a position or a velocity(or both.) It means we cannot measure one without disturbing the other, thus rendering said other unmeasurable at the point of the first measurement. It isn't really an interesting statement, because it quite likely says more about the likely somewhat wrong nature of the math we're using to describe the subatomic world than about reality. Fifth, relativity is not actually certain. It is easy to say "there is no privileged point of view" if you've never seen one, but that doesn't mean you've proven there isn't one. Yes, it is true that either here or there as we know it within our universe, there is no priviliged point of view. Human beings have an amusing capacity for seeing a limited distance and making grand pronouncements about all of existence, known and unknown alike. What are the most important principles in mathematics and science(they are not the same,) for real? We don't know for sure, but it is quite likely that a slightly revised thermodynamics is one, that the real situation(presently unknown) regarding P->NP is another, and that we don't know enough to say much else. -- 'God dammit, your posts make me hard.' --LilDebbie
 core computing problem? (none / 1) (#128) by nml on Fri Sep 02, 2005 at 02:06:10 AM EST

 That said, it [undecidability] is not a significant problem anymore, and hasn't been for a long time, because algorithms are no longer the core problem of computing. while i agree with your criticisms of the article, i think that you probably go too far in dismissing undecidability. What is a core problem of computing if not determining what can be computed? Also, you cite the P=NP problem as an important principle. Undecidability is a more fundamental (and hence probably more 'important') principle since it classes algorithms on whether they can be solved or not, instead of how efficiently they can be solved. [ Parent ]
 Well... (none / 0) (#156) by trhurler on Fri Sep 02, 2005 at 08:44:39 PM EST

 No. Really, it is fairly easy in practice to verify that an algorithm does what you want regarding halting, so undecidability has little if any real impact on the world. On the other hand, it is so far impossible to determine anything interesting about P=NP, and the latter would have HUGE real world implications immediately were it found to be true. Among other things, there would apparently be no such thing as digital privacy, ever again, period. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 you only claim that... (none / 0) (#161) by nml on Sun Sep 04, 2005 at 05:34:44 AM EST

 because undecidability has been so thoroughly explored. Otherwise we'd still have people trying to write program checkers that detect infinite loops. I think you're ignoring the contributions that undecidability and the halting problem have already made, particularly in the area of programming languages. the latter would have HUGE real world implications immediately that's a pretty common claim, but i'm not so sure. What if, hypothetically, some smart person came up with a very obscure proof that P=NP, that gave no hint how to solve factorisation efficiently? Or better yet, proposes a polynomial time solution for factorisation that takes far longer than existing algorithms when the keylength is less than 1010? We could still happily use it knowing that all known algorithms take some absurdly long time to break the encryption. Of course, someone could invent a better factorisation algorithm, but that's exactly the same situation we're in now. There'd be a lot of people screaming that the digital sky was about to fall, but really, nothing would change. Interestingly, something like this happened in algorithms to construct suffix trees. The best known algorithms were O(nlogn) with respect to the string size for a long time, but someone broke through and showed an algorithm that was O(n). Of course, that didn't actually change anything, because their algorithm was much slower than the previous algorithms for all reasonable string sizes. It just changed the complexity written in science papers, not much else. [ Parent ]
 No, really (none / 0) (#171) by trhurler on Tue Sep 06, 2005 at 02:22:57 AM EST

 First of all, depending on what your prover has access to, proving that many loops either terminate or never do is quite easy. Not ALL loops, but many, and almost all the ones that people actually write. Second, you don't seem to understand. If P = NP, it isn't just that things might be doable faster. It is that a great many things are probably doable that aren't right now. You can parallelize an awful lot of most polynomial algorithms' grunt work. The same is not true of, say, the travelling salesman problem as one NP example - unless you can find a polynomial representation, it is essentially a very hard serial problem which must be solved as such. Translate to crypto: find a P representation for certain NP problems(more than just one, depending on the cryptography in question, but a small set,) and all of a sudden, cracking cryptographic algorithms is no longer a matter of time, but merely one of money. Nothing worth protecting would go untouched. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 sorry (none / 0) (#177) by nml on Tue Sep 06, 2005 at 07:55:59 PM EST

 If P = NP, it isn't just that things might be doable faster. It is that a great many things are probably doable that aren't right now. sorry, but this is absolute bullshit. As i pointed out before, if a problem is in NP then it has a known solution (otherwise it may be undecidable), just one that can potentially take a long time. This may render them unsolvable from a practical point of view, but in theory, they can be solved. The theoretical advance of proving that P=NP is not going to change this situation at all! It's not likely to make factorisation for current keylengths faster, so it won't destroy current cryptography. So it would be a massive theoretical advance, but it wouldn't change much back in the real world. You can parallelize an awful lot of most polynomial algorithms' grunt work. The same is not true of, say, the travelling salesman problem as one NP example the parallelisation of algorithms is not related to their P/NP status at all. Factorisation is perfectly parallelisable (just ask those distrubuted computing projects) but is still in NP. Once again, the thing that would really change crypto is a fast factorisation algorithm, and proving P=NP is highly unlikely to provide that. cracking cryptographic algorithms is no longer a matter of time, but merely one of money cracking crypto has always been about time and money (they trade off), and always will be. [ Parent ]
 Er... (none / 0) (#180) by trhurler on Wed Sep 07, 2005 at 01:09:09 AM EST

 First of all, your claim that any P = NP solution is likely to be very inefficient has no basis whatsoever in fact. Second, the parallelization of most NP problems requires using the absolute least efficient methods. For instance, you can parallelize factoring, but the best method is basically no better than just dividing up the search space into chunks and sending them to separate processors. This is nowhere near as efficient as a sieve algorithm, which is essentially unfactorizable because the next result always depends on the current result. (Actually, you can parallelize the sieve "sort of," but it ends up being about as efficient as the "stupid" solution.) A P solution SHOULD be massively parallelizable in an efficient manner. Third, the trick about the time/money tradeoff in crypto is this: you have to obtain a low enough multiple of the two that you can divide by a sum of money you have to get a reasonable period of time. Better algorithms are how you do it. In this way, P=NP is quite likely to be huge. You apparently have no notion of just how huge the workload for each iteration of the algorithm would have to be to make converting NP to P a bad deal in this case. (Not to mention the little detail that a polynomial solution can be partially solved in advance of even knowing the actual inputs in many cases.) -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 breifly... (none / 0) (#189) by nml on Thu Sep 08, 2005 at 02:22:31 AM EST

 First of all, your claim that any P = NP solution is likely to be very inefficient has no basis whatsoever in fact. i think this is really the crux of the matter. I'm claiming that your assertion that P=NP will provide efficient algorithms to solve factorisation is baseless. You automatically assume that factorisation will go faster under P=NP, but i don't think this is the case, and i also think the burden on proof is on you. Just because an algorithm is polynomial time, doesn't mean it runs in an acceptable period of time, or even faster than an NP algorithm (i gave an example earlier of suffix tree construction not benefiting from a complexity advance). What it does mean that as the input size (key length in this case) gets bigger, the time taken to solve it becomes worse somewhat more slowly. And polynomial time covers a lot of algorithms that still get worse very fast, like n100. So answer me this: how will P=NP make factoring my 512-bit RSA public key go any faster? Your point about parallelism is interesting. I don't believe that P==parallelisable and NP==not (i believe it depends heavily on the problem), but i don't think i'm well versed enough in the area to refute you. However, parallelism is certainly not a panacea - a problem that takes a long time is still a problem that takes long time (money/time tradeoff again). You apparently have no notion of just how huge the workload for each iteration of the algorithm would have to be to make converting NP to P a bad deal in this case. no, i'm pointing out that you have no idea how long the P algorithm is going to take once you get there. O notation only tells you at what rate things get slower, not how fast they go in the first place. Human history suggests that algorithms for factorisation ARE NOT FAST! The only thing that will make factorisation go faster is (surprise!) faster factorisation algorithms. P=NP will not automatically make factorisation easier. [ Parent ]
 Hmm (none / 0) (#191) by trhurler on Thu Sep 08, 2005 at 08:03:02 PM EST

 You automatically assume that factorisation will go faster under P=NP Which isn't exactly a novel suggestion. , but i don't think this is the case, and i also think the burden on proof is on you. We both know nothing here can be PROVEN unless someone proves that P=NP, which hasn't been done. That notwithstanding, consider what it would require in order for factorization of large numbers to be slower using a P algorithm: what this would mean is that the P algorithm in question has a unit work time that is a very substantial fraction of the NP workload for solving the same problem. For AES 256, the current time to break is somewhere in the billions of years. You think an algorithm that uses a polynomial with 256n + m(m, n being constants related to the algorithm,) terms is going to take billions of years to run? There's no proof either way, but your suggestion is rather unintuitive to say the least. The suffix tree issue is a nonstarter; the difference between n(log n) and 1 is only really huge for very, very large inputs, whereas the difference between P and NP is huge for even modest inputs, and is absolutely ridiculous for large inputs(such as numbers with several hundred bits in their binary representations.) polynomial time covers a lot of algorithms that still get worse very fast, like n100. No. n100 for large problems is basically n. Large means the value of n is - wait for it - large! Your point about parallelism is interesting. I don't believe that P==parallelisable and NP==not Neither does anyone else. The issue is whether it is feasible rather than whether it is possible. If parallelism means using an algorithm with a higher order of complexity, then you're probably better off avoiding it, which is the case with factoring UNLESS you can afford or can wrangle the use of so many machines as to be silly(ie, the various crypto challenges.) no, i'm pointing out that you have no idea how long the P algorithm is going to take once you get there. O notation only tells you at what rate things get slower, not how fast they go in the first place. Look at it this way. If it takes a billion years to factor a number with n bits using the NP solutions available, and let's say n is maybe 1024(I think this would take a lot longer actually, but that's irrelevant to the example,) then in order for a P algorithm to take a billion years to solve the same problem, the P algorithm would also have to take somewhere on the order of a million years to factor the trivial 1 bit number. Do you believe such a thing is likely? If not, then you don't believe your own claim is likely. Human history suggests that algorithms for factorisation ARE NOT FAST! No algorithm on polynomials has ever been even within a few orders of magnitude as inefficient as the one you're proposing. The only thing that will make factorisation go faster is (surprise!) faster factorisation algorithms. P=NP will not automatically make factorisation easier. For sufficiently large numbers, it is actually guaranteed to do so. Whether our numbers are large enough is an open question, but it is very likely they are, as I showed above. You don't seem to understand the difference between x*n or x*n(log n) and X! for large numbers. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 [retort] (none / 0) (#192) by nml on Fri Sep 09, 2005 at 02:26:18 AM EST

 Which isn't exactly a novel suggestion. So? General agreement doesn't make something right We both know nothing here can be PROVEN unless someone proves that P=NP yes, bad choice of words. Consider yourself under a burden to show some reasonable evidence to suggest that P=NP will make factorisation go fast. No. n100 for large problems is basically n. Large means the value of n is - wait for it - large! i don't know whether you realise this, but my post had n to the power of 100, not 100 * n (sorry, i used a sup element, maybe that wasn't clear). Taking your example, pow(256, 100) is 66680144328798542740798517907212577971447583223159081603962578117640372378176320 71521432200871554290742929910593433240445888801654119365080363356052330830046095 15757951401455846307828591181402472896501613588660198169074803747646129116387737 6, which probably counts as large in my book. Look at it this way. If it takes a billion years to factor a number with n bits using the NP solutions available, and let's say n is maybe 1024(I think this would take a lot longer actually, but that's irrelevant to the example,) then in order for a P algorithm to take a billion years to solve the same problem, the P algorithm would also have to take somewhere on the order of a million years to factor the trivial 1 bit number. Do you believe such a thing is likely? If not, then you don't believe your own claim is likely. No, thats not the case at all. Lets say our current NP algorithm has time = pow(n, n / 100). For 1024 this gives time = 1267650600228229401496703205376, which can represent a billion years or whatever. Now, if i have a P algorithm time = pow(n, 100), the time taken at n = 1024 is much much larger than that, despite the P algorithm having better complexity than the NP one. Note that they both factor a 1 bit number in a small amount of time. The P algorithm will eventually be more efficient (after n = 10000), but below that, the NP algorithm is. For sufficiently large numbers, it is actually guaranteed to do so. yes, of course Whether our numbers are large enough is an open question, but it is very likely they are, as I showed above. You don't seem to understand the difference between x*n or x*n(log n) and X! for large numbers You argued that a P algorithm would have to have a large constant cost to be more costly than an NP algorithm, which is untrue as shown by my example. You might like to think about that before accusing me of not knowing the difference between growth rates of factorials and products. I'm aware that you're going to argue that my example is contrived, and that surely 1024-bit numbers are large enough for a P algorithm to be faster. However, i note, that not only has this P algorithm not yet been invented, but many people doubt whether it actually exists at all. So don't you think it's a bit early to presume that P=NP will automatically give faster factorisation? Put in a slightly different perspective, an awful lot of people have had a go at factorisation, and none have come up with a P algorithm. Many very informed people don't think a P algorithm exists. Why do you then think it unlikely, if a P algorithm is invented, that it will have some horrendous (but polynomial) complexity? It's possible that some genius will think of something simple that will result in a simple, fast algorithm, but it seems far more likely to me that someone who works at it a long time will come up with some ridiculous transform that just creeps the algorithm into P time, but remains extremely expensive to compute. Now, i don't expect you to agree with my assessment of how probable this all is, but i do think you should concede that proving P=NP won't automatically render public-key cryptography useless in a practical sense, unless it's accompanied by a fast factorisation algorithm (two seperate things). [ Parent ]
 Interestingly, (none / 0) (#194) by warrax on Sat Sep 10, 2005 at 07:24:28 AM EST

 once a polynomial time algorithm has been found for a given problem, the exponent tends to go down dramatically once more people start working on finding more efficient algorithms. (This is obviously mostly only true for problems from Real Life where the efficiency of solutions matters...) -- "Guns don't kill people. I kill people."[ Parent ]
 and moreover (none / 0) (#195) by warrax on Sat Sep 10, 2005 at 07:34:20 AM EST

 I don't seem to recall seeing any algorithm of practical importance ever having any exponent over 5 or so. Of course there are lots of P algorithms I've never seen, but all the standard graph/network flow/etc. algorithms I've seen fall within O(n^k), k<=5. Btw: This wasn't an attempt to (nor does it) invalidate your point, I'm just sayin'... -- "Guns don't kill people. I kill people."[ Parent ]
 yeah (none / 0) (#196) by nml on Mon Sep 12, 2005 at 04:10:08 AM EST

 I don't seem to recall seeing any algorithm of practical importance ever having any exponent over 5 or so. Of course there are lots of P algorithms I've never seen, but all the standard graph/network flow/etc. algorithms I've seen fall within O(n^k), k<=5. sure, i don't think you're going to find algorithms with the complexity in my example in current practice. But i'll reiterate my point about the P=NP algorithm not having been invented yet, suggesting that it's not unreasonable to think that, if it exists, it may not be like current algorithms. i get irritated when people claim that everything will be easy once someone comes along and sprinkles some magic P=NP dust, as opposed to plenty of smart people who've already spent lots of time optimising factorisation. [ Parent ]
 agreed \$ (none / 0) (#197) by warrax on Mon Sep 12, 2005 at 05:51:08 AM EST

 -- "Guns don't kill people. I kill people."[ Parent ]
 Re: the most important things? (none / 0) (#131) by chato on Fri Sep 02, 2005 at 04:43:11 AM EST

 I guess we will never agree in which are the most important principles of science. There are so many ways of doing the classification that it's impossible. I just consider these four things as important and I think there is a relationship between them. I understand that undecidability is not input validation and I can't see why you think I am implying this, it was just an example for non-programmers to understand the motivation for wanting a proof of program's correctness. As for uncertainty, I think I explain exactly what you said: you can't measure one without disturbing the other. As for relativity, note that I am refering mostly to classical relativity of motion, which is older than Einstein's. [ Parent ]
 Oh, by the way, (none / 0) (#155) by trhurler on Fri Sep 02, 2005 at 08:43:03 PM EST

 Proving the correctness of programs is an active field of research with some great results. Any program in existence in Turing's day can trivially be proven correct or otherwise over its entire input range, including a solution for whether it halts(although this requires more information than Turing realized.) Of course, programs were fairly simple then. And regarding uncertainty, you don't seem to understand: according to QM theorists, uncertainty isn't just a matter of our capability, but is inherent in nature. This is, to say the least, one of the less likely claims they make. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 Uncertainty (none / 0) (#166) by chato on Mon Sep 05, 2005 at 03:48:31 AM EST

 I included both (uncertainty in measurement and "inherent" uncertainty) in the errata page. I focus on uncertainty of measurement here because it is easier to understand. [ Parent ]
 Relativity (none / 1) (#135) by benna on Fri Sep 02, 2005 at 05:04:29 AM EST

 Relativity is as proven as any scientific theory ever is.  It is not a proof in the mathetmatical sense, but it hasn't been falsified.  That's how science works.  Don't fall down the path of the Intelligent Design people who say because evolution isn't proven it isn't true as far as science is concerned. - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Um (none / 0) (#154) by trhurler on Fri Sep 02, 2005 at 08:40:47 PM EST

 I didn't say relativity isn't real. What I said is that our present understanding of it may or may not be. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 nope, you're wrong (none / 1) (#160) by bcrowell on Sat Sep 03, 2005 at 05:19:16 PM EST

 Ah, another "expert" . . . (none / 0) (#169) by trhurler on Tue Sep 06, 2005 at 01:53:16 AM EST

 computers don't have numbers, either (none / 1) (#167) by tgibbs on Mon Sep 05, 2005 at 11:40:34 AM EST

 Computers don't have letters. They only have numbers. A letter is simply a representation on your screen of what to the computer is in fact a number. Actually, computers only have electrical states. Those can be interpreted as letters or numbers, depending upon the intent of the programmers. It is no more valid to interpret the electrical state of a memory location as a number than as a letter. [ Parent ]
 I hate to break this to you, (2.33 / 3) (#170) by trhurler on Tue Sep 06, 2005 at 01:56:51 AM EST

 But at a hardware level, our computers have algorithms wired in that presume the electrical states represent numbers. Yes, down below that level of abstraction they are merely charge quantities, and beyond that they're quantum mechanical oddities, and so on. Nevertheless, the most basic useful abstraction in a computer is a number. Nobody(and I do mean nobody - go ask an engineer at AMD or Intel,) designs processors by thinking about charge quantities. They think about numbers. The designs reflect numbers. An ALU manipulates numbers. Registers are sized according to the desired maximum number to be stored in them. Memory is indexed using numbers. I could go on forever like this, but if you haven't gotten it yet, then you're not going to get it. -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 algorithms (2.00 / 2) (#185) by tgibbs on Wed Sep 07, 2005 at 11:23:09 AM EST

 But at a hardware level, our computers have algorithms wired in that presume the electrical states represent numbers. Some operations are more useful for numbers, others for letters, boolean true/false flags, linked lists, or other logical structures. The interpretation and the choice of which operations to use is left up to the programmer. The most fundamental level is boolean logical operations, which can be used to construct arithmetic number manipulation operations as well as character manipulation operations. [ Parent ]
 Look idiot (2.00 / 2) (#187) by trhurler on Wed Sep 07, 2005 at 08:35:32 PM EST

 When you find text manipulation or linked list or similar operations designed into a general purpose CPU, let me know. Even then you'll be wrong, but in a more subtle way than you are right now, which is to say "totally obviously wrong." -- 'God dammit, your posts make me hard.' --LilDebbie[ Parent ]
 math vs. meta-math (none / 0) (#143) by HKDD on Fri Sep 02, 2005 at 02:34:26 PM EST

 In your errata article, you write certain important theorems cannot be proved. Which ones?(rhetorical question) In the same paragraph you write it is possible to construct an arithmetical statement which, if the theory is consistent, is true but not provable or refutable in the theory.  So, the assumption is that if you have a well formed formula in the Principia Mathematica, you must have an "arithmetical statement."  But that is false.  The statement "p cannot be proved," however "represented " or "encoded" in the PM, is NOT an arithmetical statement.  Arithmetical statements have a certain characteristic:  They are statements about numbers.  This "p cannot be proved" statement is NOT a statement about numbers. But, I hear you saying "p cannot be proved" IS a statement about numbers if you take the time to read Godel's paper(suprise, suprise, there is no actual "incompleteness theorem").  I answer, maybe it is a statement about numbers, but the only way one can interpret it as "true" is to use meta-mathematical considerations, which would NOT be part of ANY arithmetical system. Let me put it another way:  see footnote 9 in the text In other words, the above-described procedure provides an isomorphic image of the system PM in the domain of arithmetic, and all metamathematical arguments can equally well be conducted in this isomorphic image Here's another quote from the paper:  So the proposition which is undecidable in the system PM yet turns out to be decided by metamathematical considerations. This is where Wittgenstein et. al. dig into the interpretation that "mathematical knowledge may be incomplete."  Why is it the case that ALL metmathematical arguments can be conducted in the PM?(rhetorical question, believeing in Platonic ideals makes the argument seem "intuitionistically unobjectionable," however, accepting the efficacy of logical positivism makes the argument very objectionable) PM may be isormophic with the domain of arithmetic, but why would arithmetic be isomorphic with meta-arithmetic?(yet another rhetorical question) In any case, EVERY MATHEMATICAL THEOREM is PROVABLE. You can't escape the danger!
 Godel was a platonist n/t (none / 0) (#149) by benna on Fri Sep 02, 2005 at 07:31:07 PM EST

 - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 he is wrong about the theorems (none / 1) (#164) by modmans2ndcoming on Sun Sep 04, 2005 at 04:22:12 PM EST

 What he should have said is that Mathematic Axioms cannot be proven. Axioms are by their nature assumed truths that we base everything on. all Theorems in math have either been proven or rejected, and no one bases any proof on a conjecture unless they are doing research into the nature of the conjecture in order to try to formulate the proof of the conjecture. [ Parent ]
 True, but incomplete (pun intended) (none / 0) (#198) by rpresser on Mon Sep 12, 2005 at 02:57:57 PM EST

 Yes, math axioms cannot be proven because they are by their nature assumed truths. But Goedel went further than that. Goedel's first theorem states that there for any sufficiently powerful set of axioms, there will remain additional propositions, other than the set of axioms, for which no proof can be constructed. Therefore those statements must either be taken as axioms or else ignored. ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 Is it logic? (none / 0) (#168) by xee on Tue Sep 06, 2005 at 01:19:35 AM EST

 "If to get snow we need rain and low temperatures, and the weather is warm, then there will not be snow." Lets look at this a little closer... At a most general level, this is an implication, P -> Q P = to get snow we need rain and low temperatures, and the weather is warm Q = there will not be snow P can be further decomposed into a conjunction, ((R AND L) -> S) AND T R = there is rain L = there is a low temperature S = there will be snow = NOT Q T = the weather is warm = NOT L Remember, P = ((R & L) -> S) & NOT L Refactoring these statements we can see the argument structure... Premise 1:  (R & L) -> NOT Q Premise 2:  NOT L conclusion: Q This is an invalid argument.  Q can not be concluded from these two premises.  This argument employs the fallacy I like to call Modus Foolins.  With an implication, P -> Q, negating the P does NOT imply the negation of Q.  In other words, this type of argument is completely bogus... P -> Q NOT P therefore, NOT Q. For example, allow me to state that Q = NOT P This yields the following... P -> NOT P NOT P therefore NOT NOT P, or just P. Here we have allowed a contradiction, P & NOT P, which is the definition of invalid! Proud to be a member.
 touch up (none / 0) (#172) by xee on Tue Sep 06, 2005 at 02:39:20 AM EST

 The last little argument where I derive a contradiction could go a little more formally... Assume: P 1: P (by assumption) 2: NOT P -> P (conditionalization) 3: NOT NOT P (Double negation on 1) 4: NOT P (Modus Foolins on 3, 2) 5: P AND NOT P (conjunction on 1, 4) Line 2 is legal by the rule that, given a true P, one may write Q -> P where Q can be anything at all. Line 4 is in error, it is wrongly justified because line 3 is the negation of the antecedent of line 2.  This does not imply the negation of line 2's consequent. Proud to be a member.[ Parent ]
 Not exactly (none / 0) (#173) by chato on Tue Sep 06, 2005 at 04:13:04 AM EST

 There is some ambiguity in the sentence "to get A, you need B and C", as i am not saying: (rain) AND (low temperature) IMPLIES (snow) I am saying: (rain) AND (low temperature) EQUIVALENT (snow) [ Parent ]
 Implication doesn't work that way! (none / 0) (#175) by Shano on Tue Sep 06, 2005 at 07:07:48 AM EST

 The original argument is sound, but your encoding is incorrect. The statement "to get snow, we need rain and low temperatures" should be encoded as "S -> R & L", not "R & L -> S". The latter is "if there is rain and it is cold, then there is snow", which is false. There could be hail, or sleet. Implication is tricky, and getting it the right way round when encoding a problem can be difficult. I had a lecturer who regularly spends time ranting about this sort of thing. [ Parent ]
 Niiice (none / 0) (#179) by xee on Tue Sep 06, 2005 at 11:13:35 PM EST

 I stand corrected.  :)  What do you think of Chato's reply...  "(rain) AND (low temperature) EQUIVALENT (snow)" ??? Proud to be a member.[ Parent ]
 Equivalence (none / 0) (#181) by Shano on Wed Sep 07, 2005 at 05:26:25 AM EST

 Well, from straight observation, it's incorrect: hail is also a possibility (snow forms slowly in the clouds and remains frozen, while hail melts and refreezes before reaching the ground). If by "equivalent", he means "if and only if", then the logic works out correctly, but can't really be applied in real life, as one of the premises is wrong. However, "to get A, you need B and C" is clearly "A -> B & C" (or one of a couple of equivalent statements). Either the logical encoding is wrong, or the original statement doesn't express the intended logic. The other cardinal sin in logic (which is really the same thing, stated differently) is assuming that (A -> B) -> (B -> A). It's a particularly easy mistake to make with reductions between problems, which frequently work in a counterintuitive fashion. [ Parent ]
 Goedel's theorem (none / 0) (#182) by Shubin on Wed Sep 07, 2005 at 07:00:12 AM EST

 It is funny, but the article shows the COMPLETE MISUNDERSTANDING of the great theorem. This text says : "the classical mathematical logic deductive system, and actually any logical system consistent and expressive enough, is not complete" What is even more funny is the fact that Kurt Goedel himself proved the fact that the "classical mathematical logic deductive system" IS complete. This was his first work on a subject. Then he tried to prove the completeness of a formal arithmetic as a next logical step. But he failed. Few days ago I had a discussion of a Goedel theorem and its meaning with a friend. After a long ICQ chat we came to a conclusion that this really interesting and complicated theorem is usually misunderstood by non-mathematicians. I have a question for you all : anybody knows who was the first idiot who told others that Goedel's theorem proves incompleteness of ANY axiomatic system, including plain real world logic ? Everyone else just repeated his stupidity, caring not about even reading the theorem text at all. No wonder. But who started this myth ?
 Twas the post-modernists n/t (none / 0) (#186) by benna on Wed Sep 07, 2005 at 05:03:29 PM EST

 - "It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein[ Parent ]
 Explanation? (none / 0) (#188) by SageGaspar on Wed Sep 07, 2005 at 09:42:09 PM EST

 I think where a lot of the disagreement comes in is that most people would agree that arithmetic is a fundamental part of whatever axiomatic system that they want to work within.Even the notions involving "grouping things" (sets), from which Russell formed his alternative to the Peano postulates, thereby bring in arithmetic and thus invoke incompleteness.The fact that they don't state it with complete precision doesn't really bother me all that much, as I do the same thing all the time with many and varied disciplines that I don't fully understand (including my own). It's part of the learning process. [ Parent ]
 Corrected in the errata long ago (none / 0) (#190) by chato on Thu Sep 08, 2005 at 04:31:08 AM EST

 I corrected this in the errata page in response to a comment by user 'citylights': "Gödel's incompleteness states that for any formal theory in which basic arithmetical facts are provable, it is possible to construct an arithmetical statement which, if the theory is consistent, is true but not provable or refutable in the theory." (source for this statement: Wikipedia). I also made a separation between boolean logic, propositional logic, and number theory in the corrected article. I think the "myth" was started by a mutation from "any axiomatic system expressive enough" (for instance, expressive enough to write theorems on natural numbers) to "any axiomatic system". [ Parent ]
 And "botanics" ... (none / 0) (#183) by kevhito on Wed Sep 07, 2005 at 10:28:46 AM EST

 ... is what, exactly?
 Botany (none / 0) (#184) by chato on Wed Sep 07, 2005 at 10:58:00 AM EST

 Corrected in the errata, thank you. [ Parent ]
 Bravo Sir (none / 0) (#200) by CookTing on Thu Nov 03, 2005 at 06:48:51 PM EST

 That's the best thing I've read since Kurt Vonnegut. And, quite possibly, the most well-written piece I've ever read on the intarwebs.
 Relativity, Uncertainty, Incompleteness and Undecidability | 200 comments (129 topical, 71 editorial, 0 hidden)
 Display: Threaded Minimal Nested Flat Flat Unthreaded Sort: Unrated, then Highest Highest Rated First Lowest Rated First Ignore Ratings Newest First Oldest First

All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.