Piero Scaruffi

These are excerpts and elaborations from my book "The Nature of Consciousness"

Incompleteness Unfortunately, a number of logical paradoxes refused to disappear, no matter how sophisticated Logic became. All of them, ultimately, are about self-reference. Oldest was the liar's paradox: the sentence "I am lying" is true if false and false if true. Bertrand Russell came up with the brilliant paradox of the class of classes that do not belong to themselves: such a class belongs to itself if it does not belong to itself and viceversa. This paradox is also known as the paradox of the barber who shaves all barbers who do not shave themselves (does he shave himself?). A variation on these paradoxes is often used to prove the impossibility of an omnipotent God: if God can do anything, can he build a rock that is so heavy that even s/he cannot lift it? Hilbert was already aware of these paradoxes, but several proposals had been made to overcome them. And several more will be proposed later (from Bertrand Russell’s “Theory of Types” of 1908 to Jon Barwise's "Situation Theory" of 1986). Nevertheless, Hilbert and others felt that Logic was capable of proving everything. Hilbert's goal was to find the procedure that would solve all possible problems. By applying that procedure, even non-mathematicians would prove difficult mathematical theorems. Hilbert was aware that, by applying inference rules of Logic to the facts that are known to be true, one could list all the other facts that follow to be true. The power of Logic seemed to be infinite. It made sense to imagine that Logic was capable of proving anything. The dream of a purely mechanical procedure for solving mathematical problems was shattered by yet another paradox, the one known as Goedel's theorem. In 1931 the (Czech-born) Austrian mathematician Kurt Goedel proved that any formal system  (containing the theory of numbers, i.e. Arithmetic) contains a proposition that cannot be proven true or false within that system (i.e., an “undecidable” proposition). Intuitively, Goedel's reasoning was that the statement "I cannot be proven" is true if and only if it cannot be proven; therefore in every system there is always at least one statement that cannot be proven, the one that says "I cannot be proven".  Neither the proposition nor its negation can be proven within the system. We can't know whether it is true or false. Predicate Logic, for example, is undecidable. Therefore any formal system built on Predicate Logic happens to be built on shaky foundations. And that includes pretty much all of classical Logic.  The conclusion to be drawn from Goedel’s theorem is catastrophic: the very concept of truth cannot be defined within a logical system. It is not possible to list all the propositions that are true. Hilbert had reduced Logic to a mechanical procedure to generate all the propositions that can be proven to be true in a theory. The dual program, of reducing Logic to a mechanical procedure to prove theorems (to prove if a proposition is true), is impossible because of Goedel’s theorem (since it is not always possible to prove that a proposition is true). This came to be known as the “decision problem”. Note that Hilbert was looking for an “algorithm” (a procedure), not a formula. For centuries most of science and Mathematics had focused on formulas. The mighty apparatus of Physics was built on formulas. All natural sciences were dealing with formulas. Hilbert, indirectly, started the trend away from formulas and towards algorithms, a trend that would become one of the salient leitmotivs of this century. A formula permits to compute a result directly from some factors by applying mathematical operations in the sequence prescribed by the priority rules of operators. An algorithm prescribes a step-by-step procedure for achieving the result. A formula is one line with an equal sign. An algorithm is made of finite steps, and the steps are ordered. Each step can be a mathematical operation or a comparison or a change in the sequence of steps. Each step can be conceived of as an “instruction” to an ideal machine capable of carrying out those elementary steps.   Back to the beginning of the chapter "Machine Intelligence" | Back to the index of all chapters