Blog Marcos L. Mucheroni Filosofia, Noosfera e cibercultura

The idea that we can solve problems by proposing a finite number of interactions between several tasks (or commands as they are called in computing languages) for several problems originates in Arithmetic.

Although the machine of Charles Babbage (1791-1871) and George Boole’s (1815-1864) Algebra make a huge contribution to modern computers, most logicians and historians of the birth of the digital world agree that the problem of fact was raised by David Hilbert’s second problem (1962-1943) at a 1900 conference in Paris.

Among 23 problems for mathematics to solve, some recently solved such as Goldbach’s Conjecture (see our post), and others to solve, the second problem was to prove that arithmetic is consistent, free from any internal contradiction.  

In the 1930s, two mathematical logicians, Kurt Gödel (1906-75) and Gerhard Gentzen (1909-1945) proved two results that called new attention to the problem proposed, both referring to Hilbert, so in fact, there is the origin of the question, roughly, if an enumerable problem is solved by a finite set of steps.

In fact, Gentzen’s solution was a proof of the consistency of Peano’s axioms, published in 1936, showing that the proof of consistency can be obtained in a system weaker than the Zermelo-Fraenkel theory, used axioms of primitive recursive arithmetic , and is therefore not general proof.

The proof of the inconsistency of arithmetic, called Gödel’s second incompleteness theorem, is more complete and shows that some proof of the consistency of Peano’s axioms can be developed without this arithmetic itself.

This theorem states: if the only acceptable proof procedures are those that can be formalized within arithmetic, then Hilbert’s problem can not be solved, in other more direct form, if the system is complete or consistent.

There are polemics raised about these results, such as Kreisel (1976) who argued that the proofs were syntactic for semantic problems, Detlefsen (1990) who says that the theorem does not prohibit the existence of a proof of consistency, and Dawson (2006) that the proof of consistency is erroneous using the evidence given by Gentzen and Gödel himself in 1958 work.

The controversies aside, Kurt Gödel’s participation in the important Vienna circle in the 1920´s before the war exploded, and the subsequent discussions of his theorem by Alain Turing (1912-1954) and Claude Shannon (1916-2001) underline its importance for the history of algorithms and modern digital computer.