The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
A Computing Procedure for Quantification Theory
Open accessAbstract
The hope that mathematical methods employed in the investigation of formal logic would lead to purely computational methods for obtaining mathematical theorems goes back to Leibniz and has been revived by Peano around the turn of the century and by Hilbert's school in the 1920's. Hilbert, noting that all of classical mathematics could be formalized within quantification theory, declared that the problem of finding an algorithm for determining whether or not a given formula of quantification theory is valid was the central problem of mathematical logic. And indeed, at one time it seemed as if investigations of this “decision” problem were on the verge of success. However, it was shown by Church and by Turing that such an algorithm can not exist. This result led to considerable pessimism regarding the possibility of using modern digital computers in deciding significant mathematical questions. However, recently there has been a revival of interest in the whole question. Specifically, it has been realized that while no decision procedure exists for quantification theory there are many proof procedures available—that is, uniform procedures which will ultimately locate a proof for any formula of quantification theory which is valid but which will usually involve seeking “forever” in the case of a formula which is not valid—and that some of these proof procedures could well turn out to be feasible for use with modern computing machinery. Hao Wang [9] and P. C. Gilmore [3] have each produced working programs which employ proof procedures in quantification theory. Gilmore's program employs a form of a basic theorem of mathematical logic due to Herbrand, and Wang's makes use of a formulation of quantification theory related to those studied by Gentzen. However, both programs encounter decisive difficulties with any but the simplest formulas of quantification theory, in connection with methods of doing propositional calculus. Wang's program, because of its use of Gentzen-like methods, involves exponentiation on the total number of truth-functional connectives, whereas Gilmore's program, using normal forms, involves exponentiation on the number of clauses present. Both methods are superior in many cases to truth table methods which involve exponentiation on the total number of variables present, and represent important initial contributions, but both run into difficulty with some fairly simple examples. In the present paper, a uniform proof procedure for quantification theory is given which is feasible for use with some rather complicated formulas and which does not ordinarily lead to exponentiation. The superiority of the present procedure over those previously available is indicated in part by the fact that a formula on which Gilmore's routine for the IBM 704 causes the machine to computer for 21 minutes without obtaining a result was worked successfully by hand computation using the present method in 30 minutes. Cf. §6, below. It should be mentioned that, before it can be hoped to employ proof procedures for quantification theory in obtaining proofs of theorems belonging to “genuine” mathematics, finite axiomatizations, which are “short,” must be obtained for various branches of mathematics. This last question will not be pursued further here; cf., however, Davis and Putnam [2], where one solution to this problem is given for ele
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Introduction to Metamathematics
Rasiowa, H. (1952) · Medical Entomology and Zoology · Cited by 4,307
Computability and Unsolvability.
Elgot, C., & Davis, M. (1959) · Mathematical Tables and Other Aids to Computation · doi:10.2307/2002808 · Cited by 980
Self-citationQuine, W. V. O. (1950) · Medical Entomology and Zoology · Cited by 482
Wang, H. (1960) · IBM Journal of Research and Development · doi:10.1147/rd.41.0002 · Cited by 331
A Proof Method for Quantification Theory: Its Justification and Realization
Gilmore, P. C. (1960) · IBM Journal of Research and Development · doi:10.1147/rd.41.0028 · Cited by 160
Cited by
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
A Machine-Oriented Logic Based on the Resolution Principle
Robinson, J. A. (1965) · Journal of the ACM · doi:10.1145/321250.321253 · Cited by 3,909
A machine program for theorem-proving
Davis, M., Logemann, G., & Loveland, D. (1962) · Communications of the ACM · doi:10.1145/368273.368557 · Cited by 3,220
Self-citationSymbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clarke, E., & Zhu, Y. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49059-0_14 · Cited by 2,150
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
The complexity of satisfiability problems
Schaefer, T. J. (1978) · Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 · doi:10.1145/800133.804350 · Cited by 1,737
Steps toward Artificial Intelligence
Minsky, M. (1961) · Proceedings of the IRE · doi:10.1109/jrproc.1961.287775 · Cited by 1,675
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
GRASP: a search algorithm for propositional satisfiability
Marques-Silva, J. P., & Sakallah, K. A. (1999) · IEEE Transactions on Computers · doi:10.1109/12.769433 · Cited by 1,374
Artificial Intelligence: A New Synthesis
(1998) · Elsevier eBooks · doi:10.1016/c2009-0-27773-7 · Cited by 1,163
Satisfiability Modulo Theories
Barrett, C., & Tinelli, C. (2018) · Handbook of Model Checking · doi:10.1007/978-3-319-10575-8_11 · Cited by 1,122
On the Complexity of Timetable and Multicommodity Flow Problems
Even, S., Itai, A., & Shamir, A. (1976) · SIAM Journal on Computing · doi:10.1137/0205048 · Cited by 1,057
QuickCheck: a lightweight tool for random testing of Haskell programs
Claessen, K., & Hughes, J. (2011) · ACM SIGPLAN Notices · doi:10.1145/1988042.1988046 · Cited by 1,011
Biere, A., Cimatti, A., Clarke, E. M., Strichman, O., & Zhu, Y. (2003) · Advances in Computers · doi:10.1016/s0065-2458(03)58003-2 · Cited by 952
Principles of Constraint Programming
Apt, K. (2003) · Cambridge University Press eBooks · doi:10.1017/cbo9780511615320 · Cited by 888
SATzilla: Portfolio-based Algorithm Selection for SAT
Xu, L., Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2490 · Cited by 857
Determining computational complexity from characteristic ‘phase transitions’
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 790
Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2006) · Journal of the ACM · doi:10.1145/1217856.1217859 · Cited by 783
(2000) · doi:10.1145/351240.351266 · Cited by 753
Test pattern generation using Boolean satisfiability
Larrabee, T. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.108614 · Cited by 703
Theory and practice of constraint handling rules
Frühwirth, T. (1998) · The Journal of Logic Programming · doi:10.1016/s0743-1066(98)10005-5 · Cited by 612
Critical Behavior in the Satisfiability of Random Boolean Expressions
Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 589
Bucket elimination: A unifying framework for reasoning
Dechter, R. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00059-4 · Cited by 583
Symbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clark, E., & Zhu, Y. (1999) · doi:10.21236/ada360973 · Cited by 537
Extending SAT Solvers to Cryptographic Problems
Soos, M., Nohl, K., & Castelluccia, C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-02777-2_24 · Cited by 484
Bucket Elimination: A Unifying Framework for Probabilistic Inference
Dechter, R. (1998) · Learning in Graphical Models · doi:10.1007/978-94-011-5014-9_4 · Cited by 452
Many hard examples for resolution
Chvátal, V., & Szemerédi, E. (1988) · Journal of the ACM · doi:10.1145/48014.48016 · Cited by 439
On the complexity of time table and multi-commodity flow problems
Even, S., Itai, A., & Shamir, A. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.21 · Cited by 431
Artificial intelligence: foundations of computational agents
(2010) · Choice Reviews Online · doi:10.5860/choice.48-2130 · Cited by 415
Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
Arnborg, S. (1985) · BIT · doi:10.1007/bf01934985 · Cited by 362
Algorithms for the maximum satisfiability problem
Hansen, P., & Jaumard, B. (1990) · Computing · doi:10.1007/bf02241270 · Cited by 360
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints
Liffiton, M. H., & Sakallah, K. A. (2008) · Journal of Automated Reasoning · doi:10.1007/s10817-007-9084-z · Cited by 329
Conflict-driven answer set solving: From theory to practice
Gebser, M., Kaufmann, B., & Schaub, T. (2012) · Artificial Intelligence · doi:10.1016/j.artint.2012.04.001 · Cited by 327
DPLL(T): Fast Decision Procedures
Ganzinger, H., Hagen, G., Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27813-9_14 · Cited by 321
Solving olympiad geometry without human demonstrations
Trinh, T. H., Wu, Y., Le, Q. V., He, H., & Luong, T. (2024) · Nature · doi:10.1038/s41586-023-06747-5 · Cited by 311
“6,42,43), resulting in highly optimized first-order logic solvers such as E (ref.”
BackgroundGenerating hard satisfiability problems
Selman, B., Mitchell, D. G., & Levesque, H. J. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00045-3 · Cited by 296
Knowledge compilation and theory approximation
Selman, B., & Kautz, H. (1996) · Journal of the ACM · doi:10.1145/226643.226644 · Cited by 295
Answer Set Solving in Practice
Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. H. (2012) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00457ed1v01y201211aim019 · Cited by 288
A survey of recent advances in SAT-based formal verification
Prasad, M. R., Biere, A., & Gupta, A. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0183-4 · Cited by 279
The Quest for Efficient Boolean Satisfiability Solvers
Zhang, L., & Malik, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_2 · Cited by 279
Solving propositional satisfiability problems
Jeroslow, R. G., & Wang, J. (1990) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01531077 · Cited by 270
Semantic Matching: Algorithms and Implementation
Giunchiglia, F., Yatskevich, M., & Shvaiko, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74987-5_1 · Cited by 259
Learning action models from plan examples using weighted MAX-SAT
Yang, Q., Wu, K., & Jiang, Y. (2007) · Artificial Intelligence · doi:10.1016/j.artint.2006.11.005 · Cited by 206
“The first class consists of exact algorithms including logical approaches [8] and integer programming approaches [24].”
BackgroundMethodSteps Toward Robust Artificial Intelligence
Dietterich, T. G. (2017) · AI Magazine · doi:10.1609/aimag.v38i3.2756 · Cited by 139
History of Interactive Theorem Proving
Harrison, J., Urban, J., & Wiedijk, F. (2014) · Handbook of the History of Logic · doi:10.1016/b978-0-444-51624-4.50004-6 · Cited by 107
HyperTree Proof Search for Neural Theorem Proving
Lample, G., Lacroix, T., Lachaux, M.-A., Rodriguez, A., Hayat, A., Lavril, T., Ebner, G., & Martinet, X. (2022) · Advances in Neural Information Processing Systems 35 · doi:10.52202/068431-1910 · Cited by 45
HyperTree Proof Search for Neural Theorem Proving
Lample, G., Lachaux, M.-A., Lavril, T., Martinet, X., Hayat, A., Ebner, G., Rodriguez, A., & Lacroix, T. (2022) · arXiv · doi:10.48550/arxiv.2205.11491 · Cited by 45
Metadata
- Authors
- Davis, M., & Putnam, H.
- Venue
- Journal of the ACM
- Published
- 1960-07
- Volume
- 7
- Issue
- 3
- Pages
- 201-215
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2062897452
- Cited by
- 2,647
- References
- 5
- FWCI
- 6.12
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.