Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-10T01:11:09.212Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPOSITIONALITY, COMPUTABILITY, AND COMPLEXITY

Part of: Computational number theory Theory of computing

Published online by Cambridge University Press:  29 June 2020

PETER PAGIN
PETER PAGIN*
Affiliation:
DEPARTMENT OF PHILOSOPHY STOCKHOLM UNIVERSITY STOCKHOLM, SWEDEN E-mail: peter.pagin@philosophy.su.se
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational explosion (factorial complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional.

Keywords

semantic compositionalityrecursive semanticscomputable semanticssemantic complexitycognitive difficulty

MSC classification

Primary: 11Y16: Algorithms; complexity
Secondary: 68Q55: Semantics

Information

Type
Research Article
Information
The Review of Symbolic Logic , Volume 14 , Issue 3 , September 2021 , pp. 551 - 591
Check for updates
Copyright
© Association for Symbolic Logic, 2020

References

Abelard, P. (2010). Logica ‘ingredientibus’. 3. Commentary on Aristotele’s De Interpretatione. In Jacobi, K. & Straub, C., editors. Corpus Christianorum Contiunatio Medievalis. Turnhout: Brepols Publishers.Google Scholar
Baader, F. & Nipkow, T. (1998). Term Rewriting and All That. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Baggio, G., van Lambalgen, M., & Hagoort, P. (2012). The processing consequences of compositionality. In Hinzen, W., Machery, E., and Werning, M., editors. The Oxford Handbook of Compositionality. Oxford: Oxford University Press, pp. 655–672.Google Scholar
Boolos, G. S., Jeffrey, R., & Burgess, J. P. (2002). Computability and Logic (fourth edition). Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Boolos, G. S. & Jeffrey, R. C. (1980). Credibility and Logic (second edition). Cambridge: Cambridge University Press. Google Scholar
Brighton, H. J. (2005). Linguistic evolution, and induction by minimum description length. In Werning, M., Machery, E., & Schurz, G., editors. The Compositionality of Concepts and Meanings: Applications to Linguistics, Psychology and Neuroscience, Vol. 2. Frankfurt/Lancaster: Ontos, pp. 13–39.Google Scholar
Bunt, H. & Muskens, R. (1999). Computational semantics. In Bunt, H., and Muskens, R., editors. Computing Meaning, Vol. 1. Amsterdam: Kluwer Academic Publishers, pp. 1–32.CrossRefGoogle Scholar
Buridan, J. & van Lecq, R. (1998). Summulae de Dialectica 4. Summulae de Suppositionibus, Vol 10. Nijmegen, Netherlands: Artistarium, p. 4.Google Scholar
Cohnitz, D. (2005). Is compositionality an a priori principle? In Werning, M., Machery, E., and Schurz, G., editors. The Compositionality of Concepts and Meanings: Foundational Issues. Frankfurt/Lancaster: Ontos, pp. 23–58.Google Scholar
Copeland, B. J. (2008). The church-turing thesis. In Zalta, E. N., editor. The Stanford Encyclopedia of Philosophy. Stanford, CA: CSLI Publications, Stanford University. Available from: http://plato.stanford.edu/archives/fall2008/entries/church-turing/.Google Scholar
Cummins, R. (1989). Meaning and Mental Representation. Cambridge, MA: MIT Press.Google Scholar
Dal Lago, U. & Martini, S. (2008). The weak lambda calculus as a reasonable machine. Theoretical Computer Science, 398, 32–50.CrossRefGoogle Scholar
Dal Lago, U. & Martini, S. (2009). On constructor rewrite systems and the lambda-calculus. In Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., and Thomas, W., editors. Automata, Languages and Programming, 36th International Colloquium, Part II. Lecture Notes in Computer Science, Vol. 5556, London: Springer, pp. 163–174.CrossRefGoogle Scholar
Davidson, D. (1965). Theories of meaning and learnable languages. In Bar-Hillel, Y., editor. Logic, Methodology and Philosophy of Science II. Amsterdam: North-Holland, pp. 1–15.Google Scholar
Davidson, D. (1967). Truth and meaning. Inquiries into Truth and Interpretation. Oxford: Clarendon Press, pp. 17–36. Originally published in Synthèse (1967), 17, 304–323.Google Scholar
Davidson, D. (1984). Inquiries into Truth and Interpretation. Oxford: Clarendon Press.Google Scholar
Fodor, J. (1987). Psychosemantics. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company.Google Scholar
Glüer, K. & Pagin, P. (2006). Proper names and relational modality. Linguistics & Philosophy, 29, 507–535.CrossRefGoogle Scholar
Glüer, K. & Pagin, P. (2008). Relational modality. Journal of Logic, Language and Information, 17, 307–322.CrossRefGoogle Scholar
Glüer, K. & Pagin, P. (2012). General terms and relational modality. Nous, 46, 159–199.CrossRefGoogle Scholar
Hartmanis, J. & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117, 285–306.CrossRefGoogle Scholar
Heim, I. & Kratzer, A. (1998). Semantics in Generative Grammar. Oxford: Blackwell.Google Scholar
Hendriks, H. (2001). Compositionality and model-theoretic interpretation. Journal of Logic, Language and Information, 10, 29–48.CrossRefGoogle Scholar
Hodges, W. (2001). Formal features of compositionality. Journal of Logic, Language and Information, 10, 7–28.CrossRefGoogle Scholar
Immerman, N. (2008). Computability and complexity. In Zalta, E. N.. editor. Stanford Encyclopedia of Philosophy. Stanford, CA: CSLI Publications, Stanford University. Available from: http://plato.stanford.edu/archives/fall2008/entries/computability/.Google Scholar
Janssen, T. M. V. (1997). Compositionality. In van Benthem, J. & Meulen, A. T., editor. Handbook of Logic and Language. Amsterdam: Elsevier, pp. 417–473.CrossRefGoogle Scholar
Li, M. & Vitányi, P. (1997). An Introduction to Kolmogorov Complexity and its Applications (second edition). New York: Springer.CrossRefGoogle Scholar
Magidor, O. (2009). Category mistakes are meaningful. Linguistics and Philosophy, 6, 553–581.CrossRefGoogle Scholar
Montague, R. (1973). The proper treatment of quantification in ordinary English. In Hintikka, J., Moravcsik, J., and Suppes, P., editors. Approaches to Natural Language. Dordrecht, Netherlands: Reidel, pp. 247–270. Reprinted in Montague 1974, page references to the reprint.Google Scholar
Montague, R. (1974). Formal Philosophy: Selected Papers by Richard Montague. New Haven, CT: Yale University Press.Google Scholar
Pagin, P. (2003). Communication and strong compositionality. Journal of Philosophical Logic, 32, 287–322.CrossRefGoogle Scholar
Pagin, P. (2012a). Communication and the complexity of semantics. In Hinzen, W., Machery, E., & Werning, M., editors. The Oxford Handbook of Compositionality. Oxford: Oxford University Press, pp. 510–529.Google Scholar
Pagin, P. (2012b). Truth-theories, competence, and semantic computation. In Preyer, G., editor. Davidson's Philosophy: A Reappraisal . Oxford: Oxford University Press.Google Scholar
Pagin, P. (2013). Compositionality, complexity, and evolution. In Lacerda, F., editor. Proceedings from a Symposium on Language Acquisition and Language Evolution. Stockholm, Sweden: PERILUS Stockholm University, Department of Linguistics. Available from: http://www.ling.su.se/perilus/perilus-2011.Google Scholar
Pagin, P. (2019a). Belief sentences and compositionality. notional part. Journal of Semantics, 36, 241–284.CrossRefGoogle Scholar
Pagin, P. (2019b). Compositionality in Davidson's early philosophy. Journal for the History of Analytical Philosophy , 7(2), 76–89.CrossRefGoogle Scholar
Pagin, P. & Westerståhl, D. (2010a). Compositionality I: Definitions and variants. Philosophy Compass, 5, 250–264.CrossRefGoogle Scholar
Pagin, P. & Westerståhl, D. (2010b). Compositionality II: Arguments and problems. Philosophy Compass, 5, 265–282.CrossRefGoogle Scholar
Pagin, P. & Westerståhl, D. (2010c). Pure quotation and general compositionality. Linguistics and Philosophy, 33, 381–415.CrossRefGoogle Scholar
Potts, C. (2007). The dimensions of quotation. In Barker, C. & Jacobson, P., editors. Direct Compositionality. Oxford: Oxford University Press, pp. 405–431.Google Scholar
Shannon, C. E. (1949). The mathematical theory of communication. In Shannon, C. E. & Weaver, W., editors. The Mathematical Theory of Communication . Chicago: The University of Illinois Press.Google Scholar
Terese. (2003). Term rewriting systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55. Cambridge: Cambridge University Press.Google Scholar
van Emde Boas, P. (1990). Machine models and simulations. In van Leeuwen, J. editor. Handbook of Theoretical Computer Science. Amsterdam: Elsevier, pp. 3–66.Google Scholar
van Rooij, I. (2008). The tractable cognition thesis. Cognitive Science, 32, 939–984.CrossRefGoogle ScholarPubMed
Werning, M. (2005). Right and wrong reasons for compositionality. In Werning, M., Machery, E., & Schurz, G., editors. The Compositionality of Concepts and Meanings: Foundational Issues. Frankfurt, Germany/Lancaster: Ontos-Verlag, pp. 285–309.CrossRefGoogle Scholar
Werning, M., Machery, E., & Schurz, G., editors. (2005). The Compositionality of Concepts and Meanings: Foundational Issues. Frankfurt, Germany/Lancaster: Ontos-Verlag, pp. 23–58.CrossRefGoogle Scholar
Westerståhl, D. (2004). On the compositional extension problem. Journal of Philosophical Logic, 35, 549–582.CrossRefGoogle Scholar