Month: April 2017

Generalizing computability theory

26 April 2017: Noah Schweber

The notion of computable function lies comfortably at the intersection of philosophy and mathematics – it describes something intuitively meaningful, and has a satisfying formalization which matches soundly with that intuition (this is Church’s thesis). However, this is true only in a restricted context, namely when we look at functions *of natural numbers*. When we try to generalize computability substantially, we run into both philosophical and mathematical problems. After saying a bit about why generalizing computability theory is something we should be interested in doing, I’ll present some approaches to generalized computability and where they run into problems (and hopefully some ideas for how to get around those problems).

Fragments of First-Order Logic for Linguistic Structures

Thomas Graf

Logic has always played a central role in the study of natural language meaning. But logic can also be used to describe the structure of words and sentences. Recent research has revealed that these structures are so simple that they can be modeled with very weak fragments of first-order logic. Unfortunately, many of these fragments are still not particularly well-understood on a formal level, which has become a serious impediment to ongoing research. This talk is thus equally about the known and the unknown: I will survey the empirically relevant fragments of first-order logic and explain how they allow for completely new generalizations about linguistic structures at the word and sentence level. But I will also highlight the limits of our current understanding and which mathematical challenges need to be overcome if the logical approach to natural language is to realize its full potential. Hopefully, an alliance of linguists, logicians, and computer scientists will be able to solve these problems in the near future.