×

zbMATH — the first resource for mathematics

Programs, grammars and arguments: A personal view of some connections between computation, language and logic. (English) Zbl 0897.03002
This interesting short paper, which is dedicated to A. Church, is an expanded version of a talk given at the 1993 LICS Meeting in Montreal. The author discusses some of the developments of the notion of computability and their relevance to linguistics and logics, with particular emphasis on his own work. The author recalls the notion of “abacus”, which he introduced in 1961 as a convenient alternative to Turing machines (based on prior work by Melzak). He also presents a more recent device (1993), suitable for generating or recognizing English sentences. Formalisms built over lambda-calculus in view of applications to linguistics are also surveyed. The author’s and P. Scott’s view of models of lambda-calculus as C-monoids is also presented. Due to the very nature of the paper, the author’s views are however only briefly sketched, which we found a little frustrating.
Reviewer: C.Berline (Paris)

MSC:
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68-02 Research exposition (monographs, survey articles) pertaining to computer science
03D20 Recursive functions and relations, subrecursive hierarchies
03D05 Automata and formal grammars in connection with logical questions
03B65 Logic of natural languages
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
03B40 Combinatory logic and lambda calculus
68Q42 Grammars and rewriting systems
68T10 Pattern recognition, speech recognition
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Deductive systems and categories III 274 pp 57– (1972)
[2] DOI: 10.1007/3-540-13346-1_7
[3] DOI: 10.4153/CMB-1961-032-6 · Zbl 0112.00902
[4] DOI: 10.1007/3-540-06859-7_148
[5] Technical Report SOC5-96.6 (1996)
[6] DOI: 10.2307/2310058 · Zbl 0080.00702
[7] DOI: 10.1090/S0273-0979-1981-14920-X · Zbl 0486.03023
[8] DOI: 10.2307/2371809 · Zbl 0063.06327
[9] Introduction to metamathematics (1952)
[10] The emperor’s new mind (1989)
[11] The L. E. J. Brouwer Centenary Symposium pp 165– (1982)
[12] Rivista di Mathematica 1 pp 256– (1891)
[13] The formulae-as-types notion of construction pp 479– (1980)
[14] Arithmetices principia, nova methodo exposita10 (1889)
[15] DOI: 10.2307/2267044 · Zbl 0034.00602
[16] DOI: 10.1016/0168-0072(94)00035-2 · Zbl 0829.18001
[17] Categorial grammars and natural language structures (1988)
[18] Type logical grammar (1988)
[19] Monatshefte für Mathematik. Phys. 38 pp 173– (1931)
[20] DOI: 10.1016/0304-3975(87)90045-4 · Zbl 0625.03037
[21] Categorial investigations (1988)
[22] DOI: 10.1016/0304-3975(86)90044-7 · Zbl 0623.03013
[23] Formal philosophy; selected papers of Richard Montague (1974)
[24] DOI: 10.2307/1970290 · Zbl 0105.00802
[25] Was sind und was sollen die Zahlen (1888) · JFM 36.0087.04
[26] DOI: 10.4153/CMB-1961-031-9 · Zbl 0112.35703
[27] American Mathematical Society Proceedings of the Symposia on Applied Mathematics 12 pp 56– (1961)
[28] Theory of algorithms (1961)
[29] Leçons de logique algébrique (1952)
[30] Semantics of natural and computer languages (1989)
[31] The calculi of lambda conversion 6 (1941)
[32] DOI: 10.1111/j.1746-8361.1969.tb01194.x · Zbl 0341.18002
[33] DOI: 10.2307/2266170 · Zbl 0023.28901
[34] DOI: 10.2307/2269031 · Zbl 0015.19301
[35] DOI: 10.1007/BF01565439 · Zbl 0014.19402
[36] Mathematische Annalen 110 pp 612– (1934)
[37] DOI: 10.1007/BFb0073962
[38] Bulletin of the American Mathematical Society 43 pp 353– (1937)
[39] Post’s machine (1983)
[40] Introduction to higher order categorical logic (1986) · Zbl 0596.03002
[41] Proceedings of the London Mathematical Society 43 pp 544– (1937)
[42] Linguistic Analysis 23 (1993)
[43] Proceedings of the London Mathematical Society 42 pp 230– (1936)
[44] DOI: 10.1007/BFb0073963
[45] DOI: 10.2307/2269030 · Zbl 0015.33901
[46] Journal of Logic, Language and Information 1 pp 141– (1992)
[47] Proceedings of the 8th LICS Conference, Montreal pp 429– (1993)
[48] DOI: 10.1016/0168-0072(88)90018-8 · Zbl 0659.18007
[49] DOI: 10.1016/S0019-9958(59)90362-6 · Zbl 0088.10801
[50] The Mathematical Intelligencer 15 (1993)
[51] Syntactic structures (1957)
[52] Categorial grammar, linguistic & literary studies in Eastern Europe 25 (1988)
[53] Mathematical Stuctures in Computer Science 3 (1993)
[54] DOI: 10.1016/0022-4049(82)90060-3 · Zbl 0485.18005
[55] Proceedings of the Symposium on Pure Mathematics 28 (1976)
[56] Proceedings of the 9th international congress of logic, methodology and philosophy of science, Uppsala 1991 (1993)
[57] From Frege to Gödel pp 302– (1923)
[58] Theoretical Linguistics 21 (1995)
[59] Proceedings International Conference on Algebra 131 pp 135– (1992)
[60] Mathematical logic (1967) · Zbl 0149.24309
[61] *-autonomous categories 752 (1979)
[62] Canadian Mathematics Bulletin 31 pp 1– (1989)
[63] DOI: 10.1145/321160.321170 · Zbl 0118.25401
[64] DOI: 10.2307/410452
[65] DOI: 10.1007/BFb0081361
[66] To H. B. Curry: Essays on combinatory logic, lambda calculus and foundations (1980)
[67] Studia Philosophica 1 pp 1– (1935)
[68] Categories in computer science and logic 92 (1987)
[69] DOI: 10.1016/0003-4843(74)90003-5 · Zbl 0282.18004
[70] The elements of mathematical logic (1950)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.