vol 4: Glossary
Site map
Directory
Search this site
Home
1: About
2: Synopsis
3: Development
Next:
Previous: Glossary: Toc
... to restore theology to the mainstream of science
The 'decision problem' (German entscheidungsproblem
[Hazewinkel, decision problem] [Borowski, decision problem]
David Hilbert (1862-1943) introduced the decision problem in his address to the International Congress of Mathematicians in 1900. His lecture "Mathematical Problems" presented 23 individual problems which he thought would be significant in the twentieth century. The tenth problem concerns us here:
Determination of the solvability of a diophantine equation. Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. David E Joyce.
The essential point of this problem is not so much the solution of Diophantine equations, but the specification of ' a process according to which it can be determined by a finite number of operations'. The decision problem is 'process dependent'. Can we decide if this process can solve this problem?
The tenth probem was solved by Alan Turing and his contemporaries. Turing, Davis. Turing devised a machine, the Turing machine, which could execute any finite logical process, and showed that there were mathematical problems, including Hilbert's tenth problem, that it could not solve. The Turing machine was the forerunner of our modern computers.
On the other hand, the very fact that computers can come to definite results shows that a large variety of decision problmes can be solved.
Further reading
Books
| Borowski, Ephraim J, and Jonathan M Borwein, HarperCollins Dictionary of Mathematics, Harper Collins 1991 'It is the immodest hope of the authors that this dictionary will not only prove valuable as a reference book for students of mathematics at all levels from secondary schools to a master's degree, but also offer much to interest a more general readership.' Amazon back |
| Casti, John L, Five Golden Rules Great: Theories of 20th-Century Mathematics - and Why They Matter, John Wiley and Sons 1996 Preface: '[this book] is intended to tell the general reader about mathematics by showcasing five of the finest achievements of the mathematician's art in this [20th] century.' p ix. Treats the Minimax theorem (game theory), the Brouwer Fixed-Point theorem (topology), Morse's theorem (singularity theory), the Halting theorem (theory of computation) and the Simplex method (optimisation theory). Amazon back |
| Chaitin, Gregory J, Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory, World Scientific 1987 Jacket: 'Algorithmic information theory is a branch of computational complexity theory concerned with the size of computer programs rather than with their running time. ... The theory combines features of probability theory, information theory, statistical mechanics and thermodynamics, and recursive function or computability theory. ... [A] major application of algorithmic information theory has been the dramatic new light it throws on Goedel's famous incompleteness theorem and on the limitations of the axiomatic method. ...' Amazon back |
| Davis, Martin, Computability and Unsolvability, Dover 1982 Preface: 'This book is an introduction to the theory of computability and non-computability ususally referred to as the theory of recursive functions. The subject is concerned with the existence of purely mechanical procedures for solving problems. ... The existence of absolutely unsolvable problems and the Goedel incompleteness theorem are among the results in the theory of computability that have philosophical significance.' Amazon back |
| Hazewinkel, Michiel, and (managing editor), Encyclopaedia of Mathematics (6 volumes), Kluwer Academic and Toppan 1995 'The Encyclopaedia of mathematics aims to be a reference work for all parts of mathematics. It is a translation with updates and editorial comments of the Soviet Mathematical Encyclopaedia published by 'Soviet Encyclopaedia Publishing House' in five volumes in 1977-85.' Amazon back |
| Reid, Constance, Hilbert-Courant, Springer Verlag 1986 Jacket: '[Hilbert] is woven out of three distinct themes. It presents a sensitive portrait of a great human being. It describes accurately and intelligibly on a non-technical level the world of mathematical ideas in which Hilbert created his masterpieces. And it illuminates the background of German social history against which the drama of Hilbert's life was played. ... Beyond this, it is a poem in praise of mathematics.' Science Amazon back |
Papers
| Chaitin, Gregory J, "Randomness and Mathematical Proof", Scientific American, 232, 5, May 1975, page 47-52. 'Although randomness can be precisely defined and can even be measured, a given number cannot be proved random. This enigma establishes a limit in what is possible in mathematics'. back |
| Post, E L, "Finite combinatory processes - formulation 1.", The Journal of Symbolic Logic, 1, 42, 1936, page 103-105. back |
| Post, Emil L, "Recursively Enumerable Sets of Positive Integers and their Decision Problems ", Bulletin of the American Mathematical Society, 50, , February 26 1944, page 284-316.. back |
| Turing, Alan, "On Computable Numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, 42, 12 November 1937, page 230-265. 'The "computable" numbers maybe described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost as easy to define and investigate computable functions of an integrable variable or a real or computable variable, computable predicates and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the rewlations of the computable numbers, functions and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine'. back |
Links
| David E Joyce Mathematical problems by David Hilbert Lecture delivered before the International Congress of Mathematicians at Paris in 1900. Dr. Maby Winton Newson translated this address into English with the author's permission for Bulletin of the American Mathematical Society 8 (1902), 437-479. A reprint of appears in Mathematical Developments Arising from Hilbert Problems, edited by Felix Brouder, American Mathematical Society, 1976. back |
| Witold Marciszewski Post's problem of creativity and 'Nature as infinite Intelligence' 'The problem of creativity was seen by Post as closely tied to that of solvability. There are problems which can be solved by mere manipulating symbols in a finite chain of steps; these do not require a creative thought. However, people successfully deal with problems which are not solvable in that way. How is it possible? How to describe the mechanism being behind such processes? What kind of logic could render and guide them?' back |
Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items
Related sites:
Concordat Watch
Revealing Vatican attempts to propagate its religion by international treaty
