Invited Paper: Programs, grammars and arguments: a personal view of some connections between computation, language and logic (at LICS 1993)

Authors: Joachim Lambek

Abstract

The question of what is an effective process or algorithm arose form the statement of Hilbert's tenth problem. It was soon seen to be related to the question of which numerical functions Nⁿ→N are computable. Among the early answers to this question the author singles out three. A numerical function is computable if and only if it is recursive, it is computable on a Turing machine, or it is definable in the untyped λ-calculus. Some aspects of the relevance of these three notions of computability to linguistics and logic, in particular, categorial logic, are discussed

BibTeX

  @InProceedings{Lambek-Programsgrammarsand,
    author = 	 {Joachim Lambek},
    title = 	 {Programs, grammars and arguments: a personal view of some connections between computation, language and logic},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {246--249},
    location =   {Montreal, Canada}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }