##
Posts Tagged ‘**Turing**’

### Posted this week (Nov 16)

Posted November 18, 2010

on:- Simon Bolivar (1783-1830): “Slavery is the worst human indignity”
- Communist but Nationalist by choice: Ho Chi Minh (1890-1969)
- Credo for optimism
- My “Mother tongue”? Can formal Arabic become a universal language?
- Aristotle’s empiricism (-384-322): Got to experiment for facts
- The “Good man” of (Confucius -551-479): Practice moral values first then, study
- Incomplete: Simplify (Einstein, Godel, Turing, Chaitin…)
- Women political prisoners: Graduating in prisons

One thing we know is that life reinforces the hypothesis that the world is infinitely complex and most of its phenomena will remain incomprehensible, meaning unexplained. For example, no theory of life evolution was able to predict the next phase in evolution and the route taken to the next phase. We don’t know if laws in biology will exist in the same meaning of laws of physics or natural phenomena.

For example, is the universe simple or complex, finite or infinite? The mathematician Chaitin answered: “This question will remain without any resolution, simply because we need an external observer outside our system of reference, preferably non-human, to corroborate our theoretical perception.” (A few of my readers will say: “This smack of philosophy” and they hate philosophy or the rational logic deducted from reduced propositions that cannot rationally be proven)

So many scholars wanted to believe that “God does not play dice” (Einstein) or that chaos is within the predictive laws of God and nature (Leibniz), or that the universe can be explained by simple, restricted set of axioms, non-redundant rules (Stephen Hawking).

Modern mathematical theories and physical observations are demonstrating that most phenomena are basically behaving haphazardly. For example, quantum physics reveals that hazard is the fundamental principle in the universe of the very tiny particles: Individual behaviors of small particles in the atomic nucleus are unpredictable; thus, there is no way of measuring accurately speed, location, and direction of a particle simultaneously; all that physics can do is assigning probability numbers.

Apparently, hazard plays a role even in mathematics. For example, many mathematical “true” statesmans cannot be demonstrated, they are logically irreducible and incomprehensible. Mathematicians know that there exists an infinity of “twin” prime numbers (odd number followed by even number) but this knowledge cannot be proven mathematically. Thus, many mathematicians would suggest to add these true “propositions” but non demonstrable theories to the basic set of axioms. Axioms are a set of the bare minimum of “given propositions” that we think we know to be true, but the reason is unable to approach them adequately, using the logical processes.

Einstein said: “What is amazing is that the eternally incomprehensible in nature is comprehensible”; meaning that we always think that we can extend an explanation to a phenomenon without being able to proving its working behaviors. Einstein wrote that to comprehend means to rationally explain by compressing the basic axioms so that our mind can understand the facts; even if we are never sure how the phenomenon behaves.

For example, Platon said that the universe is comprehensible simply because it looks structured by the beauty of geometric constructs, the regularity of the tonality in string instruments, and steady movement of planets… Steven Weinberg admits that “If we manage to explain the universal phenomenon of nature it will not be feasible by just simple laws.”

Many facts can be comprehended when they are explained by a restricted set of theoretical affirmations: This is called the Occam Razor theory which says: “The best theory or explanation is the simplest.” The mathematician Herman Weyl explained: “We first need to confirm that nature is regulated by simple mathematical laws. Then, the fundamental relationships become simpler the further we fine-tune the elements, and the better the explication of facts is more exact.”

So what is theory? Informatics extended another perspective for defining theory: “a theory is a computer program designed to taking account of observed facts by computation. Thus, the program is designed to predict observations. If we say that we comprehend a phenomenon then, we should be able to program its behavior. The smaller the program (more elegant) the better the theory is comprehended.”

When we say “I can explain” we mean that “I compressed a complex phenomenon into simple programs that “I can comprehend”, that human mind can comprehend. Basically, explaining and comprehending is of an anthropic nature, within the dimension of human mental capabilities.

The father of information theory, John von Neumann wrote: “Theoretical physics mainly categorizes phenomena and tries to find links among the categories; it does not explain phenomena.”

In 1931, mathematician Kurt Godel adopted a mental operation consisting of indexing lists of all kinds of assertions. His formal mathematical method demonstrated that there are true propositions that cannot be demonstrated, called “logically incomplete problems” The significance of Godel’s theory is that it is impossible to account for elemental arithmetic operations (addition or multiplication) by reducing its results from a few basic axioms. With any given set of logical rules, except for the most simple, there will always be statements that are undecidable, meaning that they cannot be proven or disproven due to the inevitable self-reference nature of any logical systems.

The theorem indicates that there is no grand mathematical system capable of proving or disproving all statements. An undecidable statement can be thought of as a mathematical form of a statement like “What I just said is a lie”: The statement makes reference to the language being used to describe it, it cannot be known whether the statement is true or not. However, an undecidable statement does not need to be explicitly self-reference to be undecidable. The main conclusion of Gödel’s incompleteness theorems is that all logical systems will have statements that cannot be proven or disproven; therefore, all logical systems must be “incomplete.”

The philosophical implications of these theorems are widespread. The set suggests that in physics, a “theory of everything” may be impossible, as no set of rules can explain every possible event or outcome. It also indicates that logically, “proof” is a weaker concept than “true”. Such a concept is unsettling for scientists because it means there will always be things that, despite being true, cannot be proven to be true. Since this set of theorems also applies to computers, it also means that our own minds are incomplete and that there are some ideas we can never know, including whether our own minds are consistent (i.e. our reasoning contains no incorrect contradictions).

The second of Gödel’s incompleteness theorems states that no consistent system can prove its own consistency, meaning that no sane mind can prove its own sanity. Also, since that same law states that any system able to prove its consistency to itself must be inconsistent, any mind that believes it can prove its own sanity is, therefore, insane.

Alan Turing used a deeper twist to Godel’s results. In 1936, Turing indexed lists of programs designed to compute real numbers from zero to 1 (think probability real numbers). Turing demonstrated mathematically that no infallible computational procedures (algorithms) exist that permit to deciding whether a mathematical theorem is true or false. In a sense, there can be no algorithm able to know if a computer program will even stop. Consequently, no computer program can predict that another program will ever stop computing. All that can be done is allocating a probability number that the program might stop. Thus, you can play around with all kinds of axioms, but no sets can deduce that a program will end. Turing proved the existence of non computable numbers.

Note 1: Chaitin considered the set of all possible programs; he played dice for each bit in the program (0 or 1, true or false) and allocated a probability number for each program that it might end. The probability that a program will end in a finite number of steps is called Omega. The succession of numbers comprising Omega are haphazard and thus, no simple set of axioms can deduce the exact number. Thus, while Omega is defined mathematically, the succession of the numbers in Omega has absolutely no structure. For example we can write algorithm to computing Pi but never for Omega.

Note 2: Bertrand Russell (1872-1970) tried to rediscover the founding blocks of mathematics “the royal highway to truth” He was disappointed and wrote: “Mathematics is infected of non proven postulates and infested with cyclic definitions. The beauty and the terror of mathematics is that a proof must be found; even if it proves that a theory cannot e be proven”

Note 3: The French mathematician Poincaré got a price for supposedly having discovered chaos. The article was officially published when Poincaré realized that he made a serious error that disproved his original contention. Poincaré had to pay for all the published articles and for destroying them. A single copy was saved and found at the Mittag-Leffler Institute in Stockholm.