A Note of the Entscheidungsproblem, pp. 40-41 in The Journal of Symbolic Logic, Vol. 1, No. 1, March 1936

CHURCH, Alonzo

Edité par The Association for Symbolic Logic, Inc, New York, 1936

A propos de cet article

THE DECISION PROBLEM IS UNSOLVABLE. First edition, journal issue in the original printed wrappers, of Church s solution to the Entschedungsproblem ( decision problem ). "Church s paper, submitted on April 15, 1936, was the first to contain a demonstration that David Hilbert s Entscheidungsproblem i.e., the question as to whether there exists in mathematics a definite method of guaranteeing the truth or falsity of any mathematical statement was unsolvable. Church did so by devising the lambda-calculus. A few months earlier, Church had earlier shown the existence of an unsolvable problem of elementary number theory [although this was published later than the present paper], but [the offered] paper was the first to put his findings into the exact form of an answer to Hilbert s Entscheidungsproblem. Church s paper bears on the question of what is computable, a problem addressed more directly by Alan Turing in his paper On computable numbers, published a few months later (OOC). Turing s proof was via his Turing machines. "Church got it right and he got it first. By any purely quantifiable evaluation Church s contribution was at least as important as Turing s (Robert Irving Soare in Alan Turing, his work and impact, p. 67). Both the lambda-calculus and Turing machines have proved to be of seminal importance, not only for mathematical logic, but also for the development of computer science. "The decision problem was brought to the fore of mathematics by the German mathematician David Hilbert (who in a lecture given in Paris in 1900 set the agenda for much of twentieth-century mathematics). In 1928 Hilbert described the decision problem as the main problem of mathematical logic , saying that the discovery of a general decision procedure is a very difficult problem which is as yet unsolved , and that the solution of the decision problem is of fundamental importance … Hilbert s requirement that the system expressing the whole content of mathematics be decidable amounts to this: there must be a systematic method for telling, of each mathematical statement, whether or not the statement is provable in the system… The project of expressing mathematics in the form of a complete, consistent, decidable formal system became known as proof theory and as the Hilbert programme … "Unfortunately for the Hilbert programme, however, it was soon to become clear that most interesting mathematical systems are, if consistent, incomplete and undecidable … In his incompleteness theorem, [Kurt] Gödel had shown that no matter how hard mathematicians might try to construct the all-encompassing formal system envisaged by Hilbert, the product of their labours would, if consistent, inevitably be incomplete … Gödel s theorem left the question of decidability open" (Copeland, The Essential Turing, pp. 46-8). Any attempt to solve the Entscheidungsproblem hinges on exactly what is meant by saying that a function can be calculated by a finite algorithm, or that it is effectively calculable. Turing later summarized the possibilities in his thesis ( Systems of logic based on ordinals, 1939): "A function is said to be effectively calculable if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematically expressible definition. Such a definition was first given by Gödel at Princeton in 1934 . These functions are described as general recursive by Gödel . Another definition of effective calculability has been given by Church [in the present paper] . who identifies it with lambda-definability. The author has recently suggested [in On computable numbers ] a definition corresponding more closely to the intuitive idea. It was stated above that "a function is effectively calculable if its values can be found by some purely mechanical process". We may take this statement literally, understanding by a purely mechanic.

N° de réf. du vendeur 5483

Détails bibliographiques

• Titre: A Note of the Entscheidungsproblem, pp. 40-41 in The Journal of Symbolic Logic, Vol. 1, No. 1, March 1936
• Éditeur: The Association for Symbolic Logic, Inc, New York
• Date de parution: 1936
• Reliure: Hardcover
• Édition: First edition.
• Catalogues du vendeur:
  • Computers, Numerical Methods