Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T08:12:12.864Z Has data issue: false hasContentIssue false
  • English
  • Français

The Decision Problem*

Published online by Cambridge University Press:  03 November 2016

R. L. Goodstein
Get access Rights & Permissions [Opens in a new window]

Extract

There are many questions in mathematics to which an answer can be found by a purely mechanical procedure. For instance we can determine the valid statements of the class of the statements

n is prime

by the sieve of Eratosthenes; the numbers 2, 3, 4 and so on up to any assigned n are written in a row, and we begin by striking out every second number, starting with 2. Of those which are left, the first is 3 and 3 is prime. Starting with 3, we then strike out every third number, and the first of those which remain is 5, which is prime. Starting with 5 we strike out every fifth number, determining the prime 7, and so on.

Type
Research Article
Information
The Mathematical Gazette , Volume 41 , Issue 335 , February 1957 , pp. 29 - 38
Copyright
Copyright © Mathematical Association 1957

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

A lecture delivered at the 1955 meeting of the British Association for the Advancement of Science.

References

1. Church, Alonzo, “A note on the Entscheidungsproblem,” Journal of Symbolic Logic, Vol. I (1936), pp. 40–41; pp. 101–102. “An unsolvable problem of elementary number theory,” American Journal of Mathematics, Vol. 58 (1936), pp. 345–363.CrossRefGoogle Scholar
2. Gödel, Kurt, “Über formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik und Physik, Vol. 38 (1931), pp. 173–198.Google Scholar
3. Löwenheim, Leopold, “Über Möglichkeiten in Relativkalkül, Mathematische Annalen, Vol. 76 (1915), pp. 447–470.Google Scholar
4. Post, Emil L., “Introduction to a general theory of elementary pretions, American Journal of Mathematics, Vol. 43 (1921), pp. 163–185.Google Scholar
5. Presburger, M., “Über die Vollständichkeit eines gewissen System Arithmetik ganzer Zahlen, in welchem die Addition als einzige Oper hervortritt,” Comptes-rendus du I Congrès des Mathématiciens des Pays S (Warszawa, 1929), pp. 92–101 and 395.Google Scholar
6. Szmielew, Wanda, “Decision problem in group theory,” Proceeding International Congress of Philosophy (Amsterdam, 1948), fasc. 2, pp. 7 Google Scholar
7. Tarski, Alfred, A decision method for elementary algebra and geo California, 1948.Google Scholar
8. Tarski, Alfred, Mostowski, Andrzej and Robinson, Raphael M., decidable Theories, Amsterdam, 1953.Google Scholar
9. Wittgenstein, Ludwig, Tractatus logico-philosophicus, London, 1922 Google Scholar