Lunes, Mayo 2, 2011

Hilbert's Problems

           Who of us would not be glad to lift the veil behind which the future lies hidden; to cast a glance at the next advances of our science and at the secrets of its development during future centuries? What particular goals will there be toward which the leading mathematical spirits of coming generations will strive? What new methods and new facts in the wide and rich field of mathematical thought will the new centuries disclose?
History teaches the continuity of the development of science. We know that every age has its own problems, which the following age either solves or casts aside as profitless and replaces by new ones. If we would obtain an idea of the probable development of mathematical knowledge in the immediate future, we must let the unsettled questions pass before our minds and look over the problems which the science of today sets and whose solution we expect from the future. To such a review of problems the present day, lying at the meeting of the centuries, seems to me well adapted. For the close of a great epoch not only invites us to look back into the past but also directs our thoughts to the unknown future.
The deep significance of certain problems for the advance of mathematical science in general and the important role which they play in the work of the individual investigator are not to be denied. As long as a branch of science offers an abundance of problems, so long is it alive; a lack of problems foreshadows extinction or the cessation of independent development. Just as every human undertaking pursues certain objects, so also mathematical research requires its problems. It is by the solution of problems that the investigator tests the temper of his steel; he finds new methods and new outlooks, and gains a wider and freer horizon.
It is difficult and often impossible to judge the value of a problem correctly in advance; for the final award depends upon the gain which science obtains from the problem. Nevertheless we can ask whether there are general criteria which mark a good mathematical problem. An old French mathematician said: "A mathematical theory is not to be considered complete until you have made it so clear that you can explain it to the first man whom you meet on the street." This clearness and ease of comprehension, here insisted on for a mathematical theory, I should still more demand for a mathematical problem if it is to be perfect; for what is clear and easily comprehended attracts, the complicated repels us.
Moreover a mathematical problem should be difficult in order to entice us, yet not completely inaccessible, lest it mock at our efforts. It should be to us a guide post on the mazy paths to hidden truths, and ultimately a reminder of our pleasure in the successful solution.
The mathematicians of past centuries were accustomed to devote themselves to the solution of difficult particular problems with passionate zeal. They knew the value of difficult problems. I remind you only of the "problem of the line of quickest descent," proposed by John Bernoulli. Experience teaches, explains Bernoulli in the public announcement of this problem, that lofty minds are led to strive for the advance of science by nothing more than by laying before them difficult and at the same time useful problems, and he therefore hopes to earn the thanks of the mathematical world by following the example of men like Mersenne, Pascal, Fermat, Viviani and others and laying before the distinguished analysts of his time a problem by which, as a touchstone, they may test the value of their methods and measure their strength. The calculus of variations owes its origin to this problem of Bernoulli and to similar problems. 

Fermat had asserted, as is well known, that the diophantine equation
xn + yn = zn
(x, y and z integers) is unsolvable—except in certain self evident cases. The attempt to prove this impossibility offers a striking example of the inspiring effect which such a very special and apparently unimportant problem may have upon science. For Kummer, incited by Fermat's problem, was led to the introduction of ideal numbers and to the discovery of the law of the unique decomposition of the numbers of a circular field into ideal prime factors—a law which today, in its generalization to any algebraic field by Dedekind and Kronecker, stands at the center of the modern theory of numbers and whose significance extends far beyond the boundaries of number theory into the realm of algebra and the theory of functions.
To speak of a very different region of research, I remind you of the problem of three bodies. The fruitful methods and the far-reaching principles which Poincaré has brought into celestial mechanics and which are today recognized and applied in practical astronomy are due to the circumstance that he undertook to treat anew that difficult problem and to approach nearer a solution.
The two last mentioned problems—that of Fermat and the problem of the three bodies—seem to us almost like opposite poles—the former a free invention of pure reason, belonging to the region of abstract number theory, the latter forced upon us by astronomy and necessary to an understanding of the simplest fundamental phenomena of nature.
But it often happens also that the same special problem finds application in the most unlike branches of mathematical knowledge. So, for example, the problem of the shortest line plays a chief and historically important part in the foundations of geometry, in the theory of curved lines and surfaces, in mechanics and in the calculus of variations. And how convincingly has F. Klein, in his work on the icosahedron, pictured the significance which attaches to the problem of the regular polyhedra in elementary geometry, in group theory, in the theory of equations and in that of linear differential equations. 
 

Hilbert's problems are a set of (originally) unsolved problems in mathematics proposed by Hilbert. Of the 23 total appearing in the printed address, ten were actually presented at the Second International Congress in Paris on August 8, 1900. In particular, the problems presented by Hilbert were 1, 2, 6, 7, 8, 13, 16, 19, 21, and 22 (Derbyshire 2004, p. 377). Furthermore, the final list of 23 problems omitted one additional problem on proof theory (Thiele 2001).
Hilbert's problems were designed to serve as examples for the kinds of problems whose solutions would lead to the furthering of disciplines in mathematics. As such, some were areas for investigation and therefore not strictly "problems." 

1. "Cantor's problem of the cardinal number of the continuum." The question of if there is a transfinite number between that of a denumerable set and the numbers of the continuum was answered by Gödel and Cohen in their solution to the continuum hypothesis to the effect that the answer depends on the particular version of set theory assumed. The question of if the continuum of numbers be considered a well ordered set is related to Zermelo's axiom of choice. In 1963, the axiom of choice was demonstrated to be independent of all other axioms in set theory. There is universal consensus on whether these results give a solution to this problem. 

2. "The compatibility of the arithmetical axioms." Gödel's incompleteness theorem indicated that it is cannot be proven that the axioms of logic are consistent in the sense that any formal system interesting enough to formulate its own consistency can prove its own consistency iff it is inconsistent. There is no consensus if the results of Gödel and Gentzen provide a solution. 

3. Give two tetrahedra that cannot be decomposed into congruent tetrahedra directly or by adjoining congruent tetrahedra. Dehn (1900, 1902) showed that a regular tetrahedron cannot be decomposed into a finite number of congruent tetrahedra (directly or by joining congruent tetrahedra) which can be reassembled to make a cube. It follows immediately form this result that two tetrahedra cannot be decomposed, as Hilbert proposed. 

4. Find geometries whose axioms are closest to those of Euclidean geometry if the ordering and incidence axioms are retained, the congruence axioms weakened, and the equivalent of the parallel postulate omitted. This problem was solved by G. Hamel. 

5. Can the assumption of differentiability for functions defining a continuous transformation group be avoided? (This is a generalization of the Cauchy functional equation.) Solved by John von Neumann in 1930 for bicompact groups. Also solved for the Abelian case, and for the solvable case in 1952 with complementary results by Montgomery and Zippin (subsequently combined by Yamabe in 1953). Andrew Gleason showed in 1952 that the answer is also "yes" for all locally bicompact groups.
6. Can physics be axiomatized? 

7. Let alpha!=1!=0 be algebraic and beta irrational. Is alpha^beta then transcendental? In particular, are the Gelfond-Schneider constant 2^(sqrt(2)) and Gelfond's constant e^pi transcendental (Wells 1986, p. 45)? alpha^beta is known to be transcendental for the special case of beta an irrational algebraic number, as proved in 1934 by Aleksander Gelfond in a result now known as Gelfond's theorem (Courant and Robins 1996). However, the case of nonalgebraic irrational beta has not been resolved, with solutions known only for degenerate constructions such as alpha=2, beta=ln3/ln2

8. Prove the Riemann hypothesis. The conjecture has still been neither proved nor disproved. 

9. Construct generalizations of the reciprocity theorem of number theory

10. Does there exist a universal algorithm for solving Diophantine equations? The impossibility of obtaining a general solution was proven by Yuri Matiyasevich in 1970 (Matiyasevich 1970, Davis 1973, Davis and Hersh 1973, Davis 1982, Matiyasevich 1993) by showing that the relation n=F_(2m) (where F_(2m) is the (2m)th Fibonacci number) is Diophantine. More specifically, Matiyasevich showed that there is a polynomial P in n, m, and a number of other variables x, y, z, ... having the property that n=F_(2m) iff there exist integers x, y, z, ... such that P(n,m,x,y,z,...)=0

11. Extend the results obtained for quadratic fields to arbitrary integer algebraic fields. 
12. Extend a theorem of Kronecker to arbitrary algebraic fields by explicitly constructing Hilbert class fields using special values. This calls for the construction of holomorphic functions in several variables which have properties analogous to the exponential function and elliptic modular functions (Holzapfel 1995). 

13. Show the impossibility of solving the general seventh degree equation by functions of two variables.
14. Show the finiteness of systems of relatively integral functions.
15. Justify Schubert's enumerative geometry (Bell 1945).
16. Study the topology of real algebraic curves and surfaces. See Gudkov and Utkin (1978), Ilyashenko and Yakovenko (1995), and Smale (2000) for additional details.
17. Find a representation of definite form by squares.
18. Build spaces with congruent polyhedra.
19. Analyze the analytic character of solutions to variational problems.
20. Solve general boundary value problems.
21. Solve differential equations given a monodromy group. More technically, prove that there always exists a Fuchsian system with given singularities and a given monodromy group. Several special cases had been solved, but a negative solution was found in 1989 by B. Bolibruch (Anasov and Bolibruch 1994).
22. Uniformization.
23. Extend the methods of calculus of variations




Variant's of Turing Machine

Turing Machines are the simplest formally defined model which is capable of computing anything that modern computers can compute. This makes them useful for theoretical study. However, devising a Turing Machine that solves a given problem of interest is not always easy. Therefore, there exist several common variants of Turing Machines which have been proven to be equivalent in computational power to a Turing Machine, but provide much more flexibility by increasing the types of steps that can be added to an Turing Machine algorithm. Proofs that a computational model is equivalent in power to a Turing Machine generally involve showing how to construct a Turing Machine given any possible instance of the model. Sometimes devising an algorithm to solve a problem using one of these is far easier, and since we know that they can be converted to a Turing Machine, we don't need to do all that extra work.

A list of common Turing Machine variants, otherwise known as Turing Equivalent machines:

* Non Deterministic Turing Machine - A Turing Machine which may follow more than one transition per configuration.
* Multitape Turing Machine - A Turing Machine containing a finite number of tapes greater than 1.
* Universal Turing Machine - A Turing Machine that is able to store any other Turing Machine on its tape and emulates its function. This is also related to the Recursion Theorem and is one of the more broadly useful (and important) constructs in Computational Theory.
* Enumerator - A Turing Machine which has a printer attached and prints out lists of strings.

These are useful models in the Theory of Computation, but really any programming language which describes only algorithms (which is all of them, currently) could be considered a Turing Machine variant. Arbitrary languages tend to be far less useful for Theory than the aforementioned machines, so I don't list them.
Less Powerful Computational Models

Turing Machines can also describe less powerful models of computation which can solve subsets of the problems which Turing Machines can solve. These other models can be more practical in terms of hardware costs and implementation, and form the basis for the abundant simple electronic devices that far outnumber computers. Studying what these types of machines can solve is also important, because we can we can know more about their function in general than we can about Turing Machines.

Turing Machine


A Turing machine can be thought of as a primitive, abstract computer. Alan Turing, who was a British mathematician and cryptographer, invented the Turing machine as a tool for studying the computability of mathematical functions. Turing's hypothesis (also known has Church's thesis) is a widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer program can solve. There are problems that can not be solved by a Turing machine (e.g., the halting problem); thus, these problems can not be solved by a modern computer program.

A Turing machine has an infinite tape that consists of adjacent cells (or squares). On each cell is written a symbol. The symbols that are allowed on the tape are finite in number and include the blank symbol. Each Turing machine has it's own alphabet (i.e., finite set of symbols), which determines the symbols that are allowed on the tape.
The Turing machine has a tape head that is positioned over a cell on the tape. This tape head is able to read a symbol from a cell and write a new symbol onto a cell. The tape head can also move to an adjacent cell (either to the left or to the right).

A Turing machine has a finite number of states, and, at any point in time, a Turing machine is in one of these states. A Turing machine begins its operation in the start state. A Turing machine halts when it moves into one of the halt states.
When a Turing machine begins running, it is in its start state and its tape head is positioned over one of the cells on the tape; the symbol on this cell is the current symbol.

The operation of a Turing machine proceeds as follows:
  1. The Turing machine reads the tape symbol that is under the Turing machine's tape head. This symbol is referred to as the current symbol.
  2. The Turing machine uses its transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.
  3. The Turing machine changes its state to the next state, which was returned by the transition function.
  4. The Turing machine overwrites the current symbol on the tape with the next symbol, which was returned by the transition function.
  5. The Turing machine moves its tape head one symbol to the left or to the right, or does not move the tape head, depending on the value of the 'movement' that is returned by the transition function.
  6. If the Turing machine's state is a halt state, then the Turing machine halts. Otherwise, repeat sub-step #1.
It's fairly easy to create a Turing machine that converts a string on the tape from lower case to upper case. However, for many simple tasks that can be performed with a few lines of Java or C, it's difficult and tedious to create Turing machines that performs these tasks. For example, many college students find it challenging to create a Turing machine that multiplies two numbers.



Conceptually a Turing machine, like finite automata, consists of a finite control and a tape. At any time it is in one of the finite number of states. The tape has the left end but it extends infinitely to the right. It is also divided into squares and a symbol can be written in each square. However, unlike finite automata, its head is a read-write head and it can move left, right or stay at the same square after a read or write.
        



Given a string of symbols on the tape, a Turing machine starts at the initial state. At any state it reads the symbol under the head, either erases it or replaces it with a symbol (possibly the same symbol). It then moves the head to left or right or does not move it and goes to the next state which may be the same as the current state. One of its states is the halt state and when the Turing machine goes into the halt state, it stops its operation.

Formally a Turing machine is a 5-tuple T = < Q, , , q0, > , where
Q is a finite set of states, which is assumed not to contain the symbol h. The symbol h is used to denote the halt state.
is a finite set of symbols and it is the input alphabet.
is a finite set of symbols containing as its subset and it is the set of tape symbols.
q0 is the initial state.
is the transition function but its value may not be defined for certain points.
It is a mapping from Q ( {} ) to ( Q { h } ) ( {} ) { R , L , S } . 
Here denotes the blank and R, L and S denote move the head right, left and do not move it, respectively. A transition diagram can also be drawn for a Turing machine. The states are represented by vertices and for a transition ( q, X ) = ( r, Y, D ) , where D represents R, L or S , an arc from q to r is drawn with label ( X/Y , D ) indicating that the state is changed from q to r, the symbol X currently being read is changed to Y and the tape head is moved as directed by D.

Example 1 : The following Turing machine < Q1 , , , q0 , > accepts the language aba* , where Q1 = { q0, q1, q2, q3 } , = { a , b } , = { a , b } and is as given by the table below.

State (q) Input (X) Move ( (q, X) )
q0 ( q1 , , R )
q1 a ( q2 , a , R )
q2 b ( q3 , b , R )
q3 a ( q3 , a , R )
q3 ( h , , S )









A transition diagram of this Turing machine is given below. It is assumed that the tape has at the left end and the head is initially at the left end of the tape.