skip to content

Semantics and syntax: a legacy of Alan Turing

Participation in INI programmes is by invitation only. Anyone wishing to apply to participate in the associated workshop(s) should use the relevant workshop application form.

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 London Mathematical Society NM Rothschild and Sons