An unsolvable problem in elementary number theory

CHURCH, Alonzo

Edité par John Hopkins, Baltimore, Maryland, 1936

A propos de cet article

THE FIRST PROOF THAT THE ENTSCHEIDUNGSPROBLEM IS UNSOLVABLE. First edition of the first proof that the Entscheidungsproblem (?decision problem?) is unsolvable, published seven months before Alan Turing published his own independent proof in his paper ?On computable numbers, with an application to the Entscheidungsproblem.? Church?s proof was via his ?lambda-calculus?; Turing?s 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). The work of Church and Turing gave a negative answer to the problem posed by David Hilbert in 1928 of whether mathematics is ?decidable,? that is, whether there is an effective procedure to determine, for every mathematical statement, whether the statement is provable. 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. Rare in the original printed wrappers. ?Alonzo Church, in his historic [?An unsolvable problem in elementary number theory,? 1936], provides a rigorous formal characterization of what it means to be solvable by means of an algorithm, what has come to be known as Church?s Thesis. This made it possible for him to prove that one specific problem is algorithmically unsolvable. In [this] work, Church specified a finite set of premises that encapsulates this specific problem so faithfully that an algorithm for testing whether a given conclusion follows from those premises would also provide an algorithmic solution to that specific problem, although the problem is known to be unsolvable. From this conclusion Church could conclude that the Entscheidungsproblem itself is unsolvable? (Martin Davis, in ibid., p. 50). ?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 def.

N° de réf. du vendeur 4543

Détails bibliographiques

• Titre: An unsolvable problem in elementary number theory
• Éditeur: John Hopkins, Baltimore, Maryland
• Date de parution: 1936
• Reliure: Hardcover
• Édition: First edition.
• Catalogues du vendeur:
  • Computers, Numerical Methods
  • Mathematics, Analysis, Algebra