Question

1. What is Hilbert’s Program?
2. What has been proven about Hilbert’s Program?
3. What does Godel’s incompleteness theorem show?
4. What is a Turing Machine? Be able to describe its parts.
5. Given a Turing Machine description, be able to carry out a computation and show the resultant tape.

Answer 1

---> In mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early part of the 20th century, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies.

---> Starting around 1900, Hilbert developed his Programme for the Foundations of Mathematics over a number of years, up to 1930, with much of the important work and papers published in the mid 1920s.

---> Although he did not use theories of arithmetic similar to our DOR, nor the notion of Σ1 and Π1 statements, he had related notions. In particular he talked about Finitistic Mathematics which included mathematics that could be expressed in a Δ0 way, and a little more besides.

---> The starting point to Hilbert's Programme, is, as it has been elsewhere in this section, the idea that some theories such as DOR are Σ1-complete, i.e. if σ is Σ1 and true then it is provable in DOR.

---> Hilbert understood a version of this statement for his idea of finitistic mathematics, and he understood a Σ1 sentence as expressing that there is a complete computation that verifies a finitistic statement is correct.

---> Hilbert also had a notion of Π1 statements. He called them real. He understood that Π1 statements are the negations of Σ1 statements and vice versa.

---> He proposed dividing mathematics into finitistic methods, real statements and the rest, which was called ideal and based on imaginary concepts, analogous to the theory of the complex numbers.

---> Just as for complex numbers, where theories of C can have important consequences for R, a theory involving imaginary or ideal concepts can have many important real or Π1 consequences.

---> In geometry, the proof of the compatibility of the axioms can be effected by constructing a suitable field of numbers, such that analogous relations between the numbers of this field correspond to the geometrical axioms.

---> Any contradiction in the deductions from the geometrical axioms must thereupon be recognizable in the arithmetic of this field of numbers. In this way the desired proof for the compatibility of the geometrical axioms is made to depend upon the theorem of the compatibility of the arithmetical axioms.

---> What was needed, in other words, was “a direct consistency proof of analysis, i.e., one not based on reduction to another theory.”[2] This was the challenge of Hilbert’s 2nd problem and the hope of Hilbert’s program that proceeded from it.

---> Hilbert’s 2nd problem arose from a principle that had only recently emerged in his thought, namely, that “mathematical existence is nothing other than consistency.

---> Hilbert’s address was preceded by and founded on 30 years of efforts to construct rigourously the whole of mathematics, which involved the development of the following -- see Hilbert 2nd problem:

* the algebra of logic -- Boole/De Morgan/Peirce
* naive set theory -- Cantor
* the predicate calculus -- Peirce/Frege
* the axioms of arithmetic -- Frege/Dedekind/Peano
* transfinite arithmetic -- Cantor
* the axioms of geometry -- Pasch/Hilbert

---> In his 1900 lecture to the International Congress of Mathematicians in Paris, Hilbert proposed that an axiomatic treatment of any field of mathematics required the demonstration of the independence, the completeness, and the consistency of its axioms.

---> More specifically with respect to geometry, he noted that the consistency (as he put it, the “compatibility”) of the axioms of geometry could be proved by providing an interpretation of the system in the real plane. In some sense, then, the consistency of geometry could be “reduced to” (proved indirectly as a result of proving directly) the consistency of analysis.

---> Going forward from his 1900 Problems Address, Hilbert’s program sought to “pull together into a unified whole” these developments, together with abstract axiomatics and mathematical physics. His views in this regard, “exerted an enormous influence on the mathematics of the twentieth century.

---> And yet, in his 2000 Distinguished Lecture to the Carnegie Mellon University School of Computer Science, Gregory Chaitin began his remarks as follows.

I would like to make the outrageous claim, that has a little bit of truth, that actually all of this that’s happening now with the computer taking over the world, the digitalization of our society, of information in human society, you could say in a way is the result of a philosophical question that was raised by David Hilbert at the beginning of the century.

---> At the 1900 International Congress of Mathematicians in Paris, D. Hilbert presented a list of open problems.

---> The published version [a18] contains 23 problems, though at the meeting Hilbert discussed but ten of them (problems 1, 2, 6, 7, 8, 13, 16, 19, 21, 22).

What does Godel’s incompleteness theorem show?

---> Kurt Gödel showed that most of the goals of Hilbert's program were impossible to achieve, at least if interpreted in the most obvious way.

---> Gödel's second incompleteness theorem shows that any consistent theory powerful enough to encode addition and multiplication of integers cannot prove its own consistency. This presents a challenge to Hilbert's program:

* It is not possible to formalize all mathematical true statements within a formal system, as any attempt at such a formalism will omit some true mathematical statements. There is no complete, consistent extension of even Peano arithmetic based on a recursively enumerable set of axioms.

* A theory such as Peano arithmetic cannot even prove its own consistency, so a restricted "finitistic" subset of it certainly cannot prove the consistency of more powerful theories such as set theory.

* There is no algorithm to decide the truth (or provability) of statements in any consistent extension of Peano arithmetic. Strictly speaking, this negative solution to the Entscheidungsproblem appeared a few years after Gödel's theorem, because at the time the notion of an algorithm had not been precisely defined.

---> A common name given to two theorems established by K. Gödel [1]. Gödel's first incompleteness theorem states that in any consistent formal system containing a minimum of arithmetic (+,⋅, the symbols ∀,∃, and the usual rules for handling them) a formally-undecidable proposition can be found, i.e. a closed formula A such that neither A nor ¬A can be deduced within the system.

---> Gödel's second incompleteness theorem is obtained by formalizing the proof of Gödel's first incompleteness theorem.

---> This proof involves a substantial use of the properties of the arithmetization of the syntax of the system under consideration, in that formulas expressing the following statements must be deducible: 1) the system is closed with respect to the rule of contraction of the argument (modus ponens); 2) the system is closed under substitution of terms for individual variables; and 3) the truth of a formula of a form f(N)=0, where N is a natural number and f is a primitive recursive function, implies its deducibility.

---> These conditions are met for natural arithmetization, but it is possible, without altering the algorithmic features of the arithmetization (all functions and predicates remain primitive recursive), to alter it so that the formula expressing the consistency of the system (with respect to the new arithmetization) becomes deducible. In the new arithmetization, condition 1) is violated.

---> Gödel's second incompleteness theorem gives a criterion for the comparison of formal systems: If it is possible to prove the consistency of a system T in a system S, then the latter system cannot be interpreted in the former.

---> It can thus be proved that formal mathematical analysis is not interpretable in arithmetic, the theory of types is not interpretable in analysis (cf. Types, theory of), and set theory Z is not interpretable in the theory of types.

What is a Turing Machine? Be able to describe its parts.

---> A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing.

---> A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given.It consists of a head which reads the input tape.

---> A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left.

---> If the TM reaches the final state, the input string is accepted, otherwise rejected.

---> Turing machines codify directly the most basic operations of a human computor and can be realized as physical devices, up to a point.

---> Gödel took for granted that finite machines just are (computationally equivalent to) Turing machines.

A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −

* Q is a finite set of states

* X is the tape alphabet

* ∑ is the input alphabet

* δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.

* q0 is the initial state

* B is the blank symbol

* F is the set of final states

Example of Turing machine

Turing machine M = (Q, X, ∑, δ, q0, B, F) with

* Q = {q0, q1, q2, qf}
* X = {a, b}
* ∑ = {1}
* q0 = {q0}
* B = blank symbol
* F = {qf }

Tapes and Turing machines:

---> In a nutshell, a Turing machine is a finite state machine with the ability to read and write data to a tape.

---> Although we have looked at finite state machines before, a quick reminder is in order.

---> Essentially a finite state machine consists of a number of states – finite naturally! When a symbol, a character from some alphabet say, is input to the machine it changes state in such a way that the next state depends only on the current state and the input symbol.

---> You can represent a finite state machine in a form that makes it easier to understand and think about. All you have to do is draw a circle for every state and arrows that show which state follows for each input symbol.

---> For example, the finite state machine in the diagram has three states. If the machine is in state 1 then an A moves it to state 2 and a B moves it to state 3.

---> A Turing machine is a finite state machine that has an unlimited supply of paper tape that it can write on and read back.

---> There are many formulations of a Turing machine, but essentially the machine reads a symbol from the tape, which is used as an input to the finite state machine.

---> This takes the input symbol and according to it and the current state does three things:

* It prints something on the tape

* moves the tape right or left by one cell

* changes to a new state

A Turing machine can also perform a special action – it can stop or halt – and surprisingly it is this behaviour that attracts a great deal of attention.

---> For example, a Turing machine is said to recognise a sequence of symbols written on the tape if it is started on the tape and halts in a special state called a final state. What is interesting about this idea is that there are sequences that a Turing machine can recognise that a finite state machine, i.e. a Turing machine without a tape, can’t.