From “Relativity, Uncertainty, Incompleteness and Undecidability“:

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. …

Relativity says that there is no privileged, “objective” viewpoint for certain observations. … Now, if things move relative to each other, then obviously their positions at a given time are also measured relative to each other. …

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. …

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’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. …

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.

Posted on March 29th, 2006 by Scott Granneman

Filed under: commonplace book, science