Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T01:27:23.868Z Has data issue: false hasContentIssue false
  • English
  • Français

Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic

Published online by Cambridge University Press:  15 January 2014

J. Lambek
J. Lambek*
Affiliation:
Dept. of Mathematics, Mcgill University Montreal, Quebec, CanadaH3A 2K6
Get access Rights & Permissions [Opens in a new window]

Extract

As an undergraduate I was taught to multiply two numbers with the help of log tables, using the formula

Having graduated to teach calculus to Engineers, I learned that log tables were to be replaced by slide rules. It was then that Imade the fateful decision that there was no need for me to learn how to use this tedious device, as I could always rely on the students to perform the necessary computations. In the course of time, slide rules were replaced by pocket calculators and personal computers, but I stuck to my original decision.

My computer phobia did not prevent me from taking an interest in the theoretical question: what is a computation? This question goes back to Hilbert's 10th problem (see Browder [1976]), which asks for an algorithm, or computational procedure, to decide whether any given polynomial equation is solvable in integers. It quickly leads to the related question: which numerical functions f : ℕn → ℕ are computable?

While Hilbert's 10th problem was only resolved in 1970, this related question had some earlier answers, of which I shall single out the following three:

(1) f is recursive (Gödel, Kleene),

(2) f is computable on an abstract machine (Turing, Post),

(3) f is definable in the untyped λ-calculus (Church, Kleene).

These tentative answers were shown to be equivalent by Church [1936] and Turing [1936–7].

I shall discuss here some of the more recent developments of these notions of computability and their relevance to linguistics and logic. I hope to be forgiven for dwelling on some of the work I have been involved with personally, with greater emphasis than is justified by its historical significance.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 3 , Issue 3 , September 1997 , pp. 312 - 328
Copyright
Copyright © Association for Symbolic Logic 1997

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

[1935] Ajdukiewicz, K., Diesyntaktische Konnexität, Studia Philosophica, vol. 1 pp. 1–27.Google Scholar
[1953] Bar-Hillel, Y., A quasi-arithmetical notation for syntactic description, Language, vol. 29, pp. 47–58.CrossRefGoogle Scholar
[1979] Barr, M., *-autonomous categories, Springer Lecture Notes in Mathematics, vol. 752, Springer-Verlag, Berlin.CrossRefGoogle Scholar
[1995] Bhargava, M. and Lambek, J., A rewrite system of the Western Pacific, Theoretical Linguistics, vol. 21.CrossRefGoogle Scholar
[1976] Mathematical developments arising from Hilbert problems, Proceedings of the Symposium on Pure Mathematics 28 (Browder, F. E., editor), American Mathematical Society, Providence, R.I. Google Scholar
[1988] Buszkowski, W., Marciszewski, W., and van Benthem, J., Categorial grammar, linguistic & literary studies in Eastern Europe, vol. 25, John Benjamins Publishing Co., Amsterdam.Google Scholar
[1957] Chomsky, N., Syntactic structures, Mouton and Co., The Hague.Google Scholar
[1959] Chomsky, N., On certain formal properties of grammars, Information and Control, vol. 2, pp. 137–167.Google Scholar
[1936] Church, A., A note on the Entscheidungsproblem, The Journal of Symbolic Logic, vol. 1, pp. 40–41, 101–102.Google Scholar
[1937] Church, A., Combinatory logic as a semigroup, abstract, Bulletin of the American Mathematical Society, vol. 43, p. 353.Google Scholar
[1940] Church, A., A formulation of the simple theory of types, The Journal of Symbolic Logic, vol. 5, pp. 56–68.CrossRefGoogle Scholar
[1941, 1951] Church, A., The calculi of lambda conversion, Annals of Mathematical Studies, vol. 6, Princeton University Press.Google Scholar
[1952] Curry, H. B., Leçons de logique algébrique, Gauthier-Villars, Paris.Google Scholar
[1961] Curry, H. B., Some logical aspects of grammatical structure, American Mathematical Society Proceedings of the Symposia on Applied Mathematics 12, pp. 56–68.CrossRefGoogle Scholar
[1888] Dedekind, R., Was sind und was sollen die Zahlen, Braunschweig, translated in Essays on the theory of numbers , Dover Publ., New York, N.Y., 1963.Google Scholar
[1972] Girard, J.-Y., Interprétation fonctionelle et élimination des coupures dans l'arithmétique d'ordre superieur, Thèse de doctorat d'état , Paris.Google Scholar
[1986] Girard, J.-Y., The system F of variable types fifteen years later, Theoretical Computer Science, vol. 45, pp. 159–192.Google Scholar
[1987] Girard, J.-Y., Linear logic, Theoretical Computer Science, vol. 50, pp. 1–102.Google Scholar
[1931] Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik. Phys., vol. 38, pp. 173–198, translated in J. van Heijenoort, From Frege to Gödel , Harvard University Press, Cambridge, Massachusetts, 1967, pp. 596–616.CrossRefGoogle Scholar
[1934] Gödel, K., On undecidable propositions of formal mathematical systems, notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study; reprinted in M. Davis, The undecidable , Raven Press, Hewlett, N.Y., 1965, pp. 39–74.Google Scholar
[1949] Henkin, L. A., The completeness of the first-order functional calculus, The Journal ofSymbolic Logic, vol. 14, pp. 159–166.Google Scholar
[1980] Howard, W. A., The formulae-as-types notion of construction (Seldin, J. P. et al., editors), pp. 479–490.Google Scholar
[1982] Hyland, J. M. E., The effective topos, The L. E. J. Brouwer Centenary Symposium (Troelstra, A. S. and van Dalen, D., editors), North-Holland, Amsterdam, pp. 165–216.Google Scholar
[1988] Hyland, J. M. E., A small complete category, Annals of Pure and Applied Logic, vol. 40, pp. 135–165.Google Scholar
[1992] Kanazawa, M., The Lambek calculus enriched with additional connectives, Journal of Logic, Language and Information, vol. 1, pp. 141–171.Google Scholar
[1936] Kleene, S. C., General recursive functions of natural numbers, Mathematische Annalen, vol. 112, pp. 727–742.CrossRefGoogle Scholar
[1952] Kleene, S. C., Introduction to metamathematics, Van Nostrand Co., New York.Google Scholar
[1981] Kleene, S. C., The theory of recursive functions, approaching its centennial, Bulletin of the American Mathematical Society, vol. 5, pp. 43–60.CrossRefGoogle Scholar
[1958] Lambek, J., The mathematics of sentence structure, The American Mathematical Monthly, vol. 65, pp. 154–170.Google Scholar
[1961] Lambek, J., How to program an (infinite) abacus, Canadian Mathematical Bulletin, vol. 4, pp. 295–302.Google Scholar
[1972] Lambek, J., Deductive systems and categories III, Springer Lecture Notes in Mathematics, vol. 274, Springer-Verlag, pp. 57–82.Google Scholar
[1974] Lambek, J., Functional completeness of Cartesian categories, Annals of Mathematical Logic, vol. 6, pp. 259–292.Google Scholar
[1980] Lambek, J., From λ-calculus to Cartesian closed categories, (J. Seldin et al., editors), pp. 375–402.Google Scholar
[1988] Lambek, J., On the unity of algebra and logic, Categorical algebra and its applications (Borceux, F., editor), Springer Lecture Notes in Mathematics, vol. 1348, pp. 221–229.Google Scholar
[1989] Lambek, J., Grammar as mathematics, Canadian Mathematics Bulletin, vol. 31, pp. 1–17.Google Scholar
[1992] Lambek, J., On the ubiquity of Mal'cev operations, Proceedings International Conference on Algebra (Bokut, L. A. et al., editors), Contemporary Mathematics, vol. 131, pp. 135–146.Google Scholar
[1993a] Lambek, J., Some aspects of categorical logic, Proceedings of the 9th international congress of logic, methodology and philosophy of science, Uppsala 1991 (Prawitz, D., Skyrms, B., and Westerstahl, D., editors), Elsevier, Amsterdam.Google Scholar
[1993b] Lambek, J., Least fixpoints of endofunctors of cartesian closed categories, Mathematical Stuctures in Computer Science, vol. 3.Google Scholar
[1993c] Lambek, J., Are the traditional philosophies of mathematics really incompatible?, The Mathematical Intelligencer, vol. 15.Google Scholar
[1993d] Lambek, J., Production grammars revisited, Linguistic Analysis, vol. 23.Google Scholar
[1986] Lambek, J. and Scott, P. J., Introduction to higher order categorical logic, Cambridge University Press, Cambridge.Google Scholar
[1972] Introduction, Toposes, algebraic geometry and logic (Lawvere, F. W., editor), Springer Lecture Notes in Mathematics, vol. 274, Springer-Verlag, pp. 1–12.Google Scholar
[1969] Introduction, Adjointness in foundations, Dialectica, vol. 23, pp. 281–296.Google Scholar
[1989] Longo, G. and Moggi, E., Constructive natural deduction and its “modest” interpretation, Semantics of natural and computer languages (Meseguer, J. et al., editors), M.I.T. Press, Cambridge, Massachusetts.Google Scholar
[1961] Markov, A. A., Theory of algorithms, National Science Foundation, Washington, D.C. Google Scholar
[1961] Melzak, Z. A., An informal arithmetical introduction to computability and computation, Canadian Mathematical Bulletin, vol. 4, pp. 279–293.Google Scholar
[1961] Minsky, M., Recursive unsolvability of Post's problem of “tag” and other topics in theory of Turing machines, Annals of Mathematics, vol. 74, pp. 437–454.Google Scholar
[1974] Montague, R., Formal philosophy; selected papers of Richard Montague (Thomason, R. H., editor), Yale University Press, New Haven, Connecticut.Google Scholar
[1988] Moortgat, M., Categorial investigations, Groningen-Amsterdam studies in semantics, no. 9, Foris Publications, Dordrecht.CrossRefGoogle Scholar
[1988] Morrill, G., Type logical grammar, Kluwer Academic Publishers, Dordrecht.Google Scholar
[1988] Oehrle, R. T., Bach, E., and Wheeler, D. (editors), Categorial grammars and natural language structures, Reidel Publ. Co., Dordrecht.Google Scholar
[1995] Pavlović, D., On completeness and cocompleteness, Annals of Pure and Applied Logic, vol. 74, pp. 121–152.CrossRefGoogle Scholar
[1889] Peano, G., Arithmetices principia, nova methodo exposita10 , Bocca, Turin.Google Scholar
[1891] Peano, G., Sul concetto di numero, Rivista di Mathematica, vol. 1, pp. 87–102, 256–267.Google Scholar
[1989] Penrose, R., The emperor's new mind, Oxford University Press, New York.Google Scholar
[1993] Pentus, M., Lambek grammars are context free, Proceedings of the 8th LICS Conference, Montreal, pp. 429–433.Google Scholar
[1934] Péter, R., Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion, Mathematische Annalen, vol. 110, pp. 612–632.Google Scholar
[1936] Post, E., Finite combinatory processes—formulation I, The Journal of Symbolic Logic, vol. 1, pp. 103–105.Google Scholar
[1943] Post, E., Formal reductions of the general decision problem, American Journal of Mathematics, vol. 65, pp. 197–215.Google Scholar
[1996] Pucella, R. R., Production grammars, machines and syntactic translation, Technical Report SOC5-96.6, McGill School of Computer Science.Google Scholar
[1974] Reynolds, J. C., Towards a theory of type structure, Programming Symposium '74 (Robinet, B., editor), Springer Lecture Notes in Computer Science, vol. 19, Springer-Verlag, pp. 408–425.Google Scholar
[1984] Reynolds, J. C., Polymorphism is not set-theoretic, Symposium on semantics of data types (Kahn, et al., editors), Springer Lecture Notes in Computer Science, vol. 173, Springer-Verlag, pp. 145–156.Google Scholar
[1950] Rosenbloom, P. C., The elements of mathematical logic, Dover Publications, New York, N.Y. Google Scholar
[1987] Seely, R. A. G., Linear logic and coalgebras, Categories in computer science and logic (Gray, J. W. and Scedrov, A., editors), Contemporary Mathematics, vol. 92.Google Scholar
[1980] Seldin, J. P. and Hindley, J. R. (editors), To H. B. Curry: Essays on combinatory logic, lambda calculus and foundations, Academic Press, London.Google Scholar
[1963] Shepherdson, J. C. and Sturgis, R. E., Computability of recursive functions, Journal of the Association for Computing Machinery, vol. 10, pp. 217–255.Google Scholar
[1967] Shoenfield, J. R., Mathematical logic, Addison-Wesley Publishing Co., Reading Massachusetts.Google Scholar
[1923] Skolem, T., Begründung der elementaren Arithmetik durch die rekurrierende Denkweise, English translation in van Heijenoort, J., From Frege to Gödel, Harvard University Press, Cambridge, Massachusetts, 1967, pp. 302–333.Google Scholar
[1982] Thibault, M.-F., Prerecursive categories, Journal of Pure and Applied Algebra, vol. 24, pp. 79–93.Google Scholar
[1972] Tierney, M., Sheaf theory and the continuum hypothesis, Toposes, algebraic geometry andlogic (Lawvere, F. W., editor), Springer Lecture Notes in Mathematics, vol. 274, pp. 13–42.Google Scholar
[1936] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42, pp. 230–265.Google Scholar
[1937] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 43, pp. 544–546.Google Scholar
[1983] Uspensky, V. A., Post's machine, Mir Publishers, Moscow.Google Scholar