Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T02:47:44.333Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Unusual Effectiveness of Logic in Computer Science

Published online by Cambridge University Press:  15 January 2014

Joseph Y. Halpern ,
Robert Harper ,
Neil Immerman ,
Phokion G. Kolaitis ,
Moshe Y. Vardi  and
Victor Vianu
Joseph Y. Halpern
Affiliation:
Computer Science Department, Cornell University, 4144 Upson Hall, Ithaca, NY 14853, USAE-mail:[email protected]
Robert Harper
Affiliation:
Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA 15213-3891, USAE-mail:[email protected]
Neil Immerman
Affiliation:
Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USAE-mail:[email protected]
Phokion G. Kolaitis
Affiliation:
Computer Science Department, University of California, Santa Cruz, Santa Cruz, CA 95064, USAE-mail:[email protected]
Moshe Y. Vardi
Affiliation:
Department of Computer Science, Rice University, MS 132, 6100 S. Main Street, Houston, TX 77005-1892, USAE-mail:[email protected]
Victor Vianu
Affiliation:
CSE 0114, University of California, San Diego, La Jolla, CA 92093-0114, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 7 , Issue 2 , June 2001 , pp. 213 - 236
Copyright
Copyright © Association for Symbolic Logic 2001

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.)

References

REFERENCES

[1] Abiteboul, S., Hull, R., and Vianu, V., Foundations of databases, Addison-Wesley, Reading, Massachusetts, 1995.Google Scholar
[2] Abiteboul, S. and Vianu, V., Generic computation and its complexity, Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pp. 209–219.Google Scholar
[3] Büchi, J. R., On a decision method in restricted second order arithmetic, Proceedings of the International Congress on Logic, Methodology and Philosophy of Science 1960, Stanford University Press, Stanford, 1962, pp. 1–12.Google Scholar
[4] Burch, J. R., Clarke, E. M., McMillan, K. L., Dill, D. L., and Hwang, L. J., Symbolic model checking: 1020 states and beyond, Information and Computation, vol. 98 (1992), no. 2, pp. 142–170.Google Scholar
[5] Church, A., A note on the Entscheidungsproblem, The Journal of Symbolic Logic, vol. 1 (1936), pp. 40–44.CrossRefGoogle Scholar
[6] Clarke, E. M., Emerson, E. A., and Sistla, A. P., Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems, vol. 8 (1986), no. 2, pp. 244–263.Google Scholar
[7] Codd, E. F., A relational model of data for large shared data banks, Communications of the ACM, vol. 13 (1970), no. 6, pp. 377–387.Google Scholar
[8] Curry, H. B. and Feys, R., Combinatory logic, North-Holland, 1958.Google Scholar
[9] Curry, H. B., Hindley, J. R., and Seldin, J. P., Combinatory logic, Volume 2, North-Holland, 1972.Google Scholar
[10] Davis, M., Influences of mathematical logic on computer science, The universal Turing machine: A half-century survey (Herken, R., editor), Oxford University Press, 1988, pp. 315–326.Google Scholar
[11] Davis, M., The universal computer, Norton, 2000.Google Scholar
[12] Ebbinghaus, H. D. and Flum, J., Finite model theory, Perspectives in Mathematical Logic, Springer-Verlag, 1995.Google Scholar
[13] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49 (1961), pp. 129–141.Google Scholar
[14] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Karp, R. M., editor), SIAM-AMS Proceedings, vol. 7, 1974, pp. 43–73.Google Scholar
[15] Fagin, R., Halpern, J. Y., Moses, Y., and Vardi, M. Y., Reasoning about knowledge, MIT Press, Cambridge, Massachusetts, 1995.Google Scholar
[16] Fraïssé, R., Sur quelques classifications des systèmes de relations, Publ. Sci. Univ. Alger. Sér. A, vol. 1 (1954), pp. 35–182.Google Scholar
[17] Garey, M. and Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, W. Freeman and Co., San Francisco, 1979.Google Scholar
[18] Girard, J.-Y., Lafont, Y., and Taylor, P., Proofs and types, Cambridge Tracts in Theoretical Computer Science, vol. 7, Cambridge University Press, Cambridge, England, 1989.Google Scholar
[19] Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.Google Scholar
[20] Goering, R., Model checking expands verification's scope, Electronic Engineering Today, (1997).Google Scholar
[21] Gray, J., Notes on database operating systems, Operating systems: An advanced course (Bayer, R., Graham, R. M., and Seegmuller, G., editors), Lecture Notes in Computer Science, vol. 66, Springer-Verlag, Berlin/New York, 1978, also appears as IBM Research Report RJ 2188, 1978.Google Scholar
[22] Halpern, J. Y. and Moses, Y., Knowledge and common knowledge in a distributed environment, Journal of the ACM, vol. 37 (1990), no. 3, pp. 549–587.Google Scholar
[23] Hamming, R. W., The unreasonable effectiveness of mathematics, American Mathematical Monthly, vol. 87 (1980), pp. 81–90.Google Scholar
[24] Henkin, L., Monk, J. D., and Tarski, A., Cylindric algebras, Part I, North Holland, 1971, Part II, North Holland, 1985.Google Scholar
[25] Hintikka, J., Knowledge and belief, Cornell University Press, Ithaca, New York, 1962.Google Scholar
[26] Holzmann, G. J., The model checker SPIN, IEEE Transactions on Software Engineering, vol. 23 (1997), no. 5, pp. 279–295, special issue on Formal Methods in Software Practice.Google Scholar
[27] Howard, William A., The formulas-as-types notion of construction, To H. B. Curry: Essays in combinatory logic, lambda calculus and formalism (Seldin, J. P. and Hindley, J. R., editors), Academic Press, 1980, pp. 479–490.Google Scholar
[28] Immerman, N., Number of quantifiers is better than number of tape cells, Journal of Computer and System Sciences, vol. 22 (1981), no. 3, pp. 384–406.Google Scholar
[29] Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.Google Scholar
[30] Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.Google Scholar
[31] Immerman, N., Languages which capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), no. 4, pp. 760–778.Google Scholar
[32] Immerman, N., Nondeterministic space is closed under complement, SIAM Journal on Computing, vol. 17 (1988), pp. 935–938.Google Scholar
[33] Immerman, N., Dspace[nk] = var[k + 1], Proceedings of the 6th IEEE Symposium on Structure in Complexity Theory, 1991, pp. 334–340.Google Scholar
[34] Immerman, N., Descriptive complexity: a logician's approach to computation, Notices of the American Mathematical Society, vol. 42 (1995), no. 10, pp. 1127–1133.Google Scholar
[35] Immerman, N., Descriptive complexity, Springer-Verlag, 1999.Google Scholar
[36] Jacobs, B., Categorical logic and type theory, Studies in Logic and the Foundations of Mathematics, vol. 141, Elsevier, Amsterdam, 1999.Google Scholar
[37] Kanellakis, P. C., Elements of relational database theory, Handbook of theoretical computer science (Van Leeuwen, J., editor), Elsevier, 1991, pp. 1074–1156.Google Scholar
[38] Kripke, S., A semantical analysis of modal logic I: normal modal propositional calculi, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 9 (1963), pp. 67–96, announced in Journal of Symbolic Logic , vol. 24 (1959), p. 323.CrossRefGoogle Scholar
[39] Kurshan, R. P., Computer aided verification of coordinating processes, Princeton University Press, 1994.Google Scholar
[40] Kurshan, R. P., Formal verification in a commercial setting, The Verification Times, (1997).Google Scholar
[41] Lichtenstein, O. and Pnueli, A., Checking that finite-state concurrent programs satisfy their linear specifications, Proceedings of the 13th ACM Symposium on Principles of Programming Languages, 1985, pp. 97–107.Google Scholar
[42] Maier, D., The theory of relational databases, Computer Science Press, 1983.Google Scholar
[43] Manna, Z. and Waldinger, R., The logical basis for computer programming, Addison-Wesley, 1985.Google Scholar
[44] Martin-Löf, P., Intuitionistic type theory, Studies in Proof Theory, Bibliopolis, Naples, Italy, 1984.Google Scholar
[45] Mitchell, J. C., Foundations for programming languages, Foundations of Computing, MIT Press, 1996.Google Scholar
[46] Plotkin, G., A structural approach to operational semantics, Technical Report DAIMI–FN–19, Computer Science Department, Aarhus University, 1981.Google Scholar
[47] Pnueli, A., The temporal logic of programs, Proceedings of the 18th IEEE Symposium on Foundation of Computer Science, 1977, pp. 46–57.Google Scholar
[48] Queille, J. P. and Sifakis, J., Specification and verification of concurrent systems in Cesar, Proceedings of the 5th International Symposium on Programming, Lecture Notes in Computer Science, vol. 137, Springer-Verlag, 1981, pp. 337–351.Google Scholar
[49] Reynolds, John C., Three approaches to type structure, Tapsoft, Springer-Verlag, 1985.Google Scholar
[50] Reynolds, John C., Theories of programming languages, Cambridge University Press, 1998.CrossRefGoogle Scholar
[51] Silberschatz, A., Korth, H., and Sudarshan, S., Database system concepts, McGraw-Hill, 1997.Google Scholar
[52] Tarditi, David, Morrisett, Greg, Cheng, Perry, Stone, Chris, Harper, Robert, and Lee, Peter, TIL: A type-directed optimizing compiler for ML, ACM SIGPLAN Conference on Programming Language Design and Implementation, Philadelphia, Pennsylvania, 05 1996, pp. 181–192.Google Scholar
[53] Tarski, A., Der Wahrheitsbegriff in den formalisierten Sprachen, Studia Philosophica, vol. 1 (1935), pp. 261–405.Google Scholar
[54] Turing, A., On computable numbers with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 3, vol. 42 (1936/37), pp. 230–265.Google Scholar
[55] Ullman, J. D., Principles of database and knowledge base systems, Computer Science Press, 1988.Google Scholar
[56] Vardi, M. Y., The complexity of relational query languages, Proceedings of the 14th ACM Symposium on Theory of Computing, San Francisco, 1982, pp. 137–146.Google Scholar
[57] Vardi, M. Y., An automata-theoretic approach to linear temporal logic, Logics for concurrency: Structure versus automata (Moller, F. and Birtwistle, G., editors), Lecture Notes in Computer Science, vol. 1043, Springer-Verlag, Berlin, 1996, pp. 238–266.Google Scholar
[58] Vardi, M. Y. and Wolper, P., An automata-theoretic approach to automatic program verification, Proceedings of the 1st symposium on logic in computer science, Cambridge, 06 1986, pp. 332–344.Google Scholar
[59] Vardi, M. Y. and Wolper, P., Reasoning about infinite computations, Information and Computation, vol. 115 (1994), no. 1, pp. 1–37.Google Scholar
[60] Vianu, V., Databases and finite-model theory, Descriptive complexity and finite models (Immerman, Neil and Kolaitis, Phokion, editors), Dimacs Series in Discrete Mathematics and Theoreticcal Computer Science, American Mathematical Society, 1997, Proceedings of a Dimacs Workshop 01 14-17, 1996, Princeton University.Google Scholar
[61] Wigner, E. P., The unreasonable effectiveness of mathematics in the natural sciences, Communications on Pure and Applied Mathematics, vol. 13 (1960), pp. 1–14.CrossRefGoogle Scholar