skip to content
 

Semantics and Syntax: A Legacy of Alan Turing

9th January 2012 to 6th July 2012

Organisers: Arnold Beckmann (Swansea), Barry Cooper (Leeds), Benedikt Löwe (Amsterdam), Elvira Mayordomo (Zaragoza) and Nigel Smart (Bristol)

Scientific Advisory Committee: Samson Abramsky (Oxford), Steve Cook (Toronto), Jan Denef (Leuven), Martin Hyland (Cambridge), Arjen Lenstra (EPFL), Angus MacIntyre (Queen Mary), Jacques Stern (ENS Paris), and Hugh Woodin (Berkeley)

Programme Theme

In several mathematical areas of Theoretical Computer Science, we perceive a distinction between research focusing on symbolic manipulation of language and structures (independent of meaning) and research dealing with interpreted computational meaning of structures. In mathematical logic, the distinction is known as syntax (symbolic manipulation) versus semantics (interpreted structures). This distinction recurs in many research areas, often under different (and sometimes incompatible) names. For research in these fields, both views are important and fundamental for gaining full understanding of the formal issues involved. The programme Syntax and Semantics endeavours to bring together researchers from both sides of the syntax-semantics divide. We shall focus on four mathematical areas bordering computer science in which the syntax/semantics distinction is particularly relevant: logic, complexity, cryptography, and randomness.

Alan Turing Year logo

The year 2012 sees the 100th anniversary of the birthday of Alan Turing, who made fundamental contributions to our research areas and worked within both the semantic/computational and syntactic/symbolic paradigms, and managed to combine them in various applications using an integrated methodology that should serve as an example for our programme. We understand our programme as embedded in the large-scale celebration of the Alan Turing Year.

Final Scientific Report: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons