Computability history

Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

Albert Einstein: As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.

Cantor diagonalization: 1880's (infinity)
Hilbert's 23 problems: 1900
Chaos theory (Poincaré, Lorentz, etc.)
Hilbert's program: 1920 (mechanical math)
Borel: real numbers and reality 1927
Heisenberg: Uncertainty 1927

3. 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 ...

Chaitin states in his book Meta Mathematics that Émile Borel, in 1927, "pointed out that if you really believe in the notion of a real number as an infinite sequence of digits 3.1415926..., then you could put all of human knowledge into a single real number",

Chaitin refers to this Borel number concept as "Borel's amazing know-it-all real number".

More: Émile Borel

David Hilbert (German mathematician) was an influential German mathematician. In 1928, he proposed finding a consistent mathematical system that will allow all possible truths to be decided. This would allow the automatic, or mechanical, proving of all possible mathematical truths. In 1931, Gödel proved that this could not be done.
Hilbert started the separation of mathematics from philosophers (opinion truth) and reality truth. Today, (pure) mathematics is a logical truth consisting of symbol manipulation with no direct connection with reality truth or opinion truth.

More: David Hilbert

Book: On formally undecidable propositions of principia mathematica and related systems

Kurt Gödel stunned the mathematical world in 1931 by proving that it is impossible to find a consistent mathematical system that will allow all possible truths to be decided. This is called the incompleteness Theorem.
Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.

The incompleteness theorem of Kurt Gödel (Austrian logician, mathematician, philosopher) says that, for any formal proof system that includes arithmetic, there exist true statements that cannot be proven within the system. Part of Gödel's motivation was the belief that there is no finite description of truth. That is, truth is infinite.

More: Infinity beyond experience

More: Kurt Gödel

Halting problem (Turing, Turing machine, 1936): It is impossible to write a computer program that looks at another computer program (and its data) and determines whether the other computer program eventually halts or whether it loops forever.

Viruses cannot be identified with certainty.
Operating systems need user approval to shut down processes that might be important.

Possible answers for a computation of an undecidable problem are yes (true), no (false), or maybe (wait forever).

Information theorist Gregory Chaitin (determining randomness) showed that there is no algorithm for determining whether a sequence of symbols is random. One must be informed of this. That is, one must go outside the system.

This forms the basis of AIT (Algorithmic Information Theory) as in the smallest program that can output a given output.

More: Algorithmic Information Theory