Selected papers of the ''Turing Centenary Conference: CiE 2012''
University of Cambridge, UK, 2012


The seven papers in this special issue arose from the 2012 Turing Centenary Conference CiE 2012: How the World Computes, held at University of Cambridge in June 2012. CiE 2012 was the eigth meeting in the series of conferences associated with the Association for Computability in Europe.


The main aim of the Association for Computability in Europe is to promote the development, particularly in Europe, of computability-related science, ranging over mathematics, computer science, and applications in various natural and engineering sciences such as physics and biology, including the promotion of the study of philosophy and history of computing as it relates to questions of computability.

CiE 2012 was one of a series of special events, running throughout the Alan Turing Year, celebrating Turing's unique impact on mathematics, computing, computer science, informatics, morphogenesis, artificial intelligence, philosophy and the wider scientific world. Its central theme was the computability-theoretic concerns underlying the broad spectrum of Turing's interests, and the contemporary research areas founded upon and animated by them. In this sense, CiE 2012, held in Cambridge in the week running up to the centenary of Turing's birthday, dealt with the essential core of what made Turing's contribution so influential and long-lasting.

As is usual in computer science, CiE 2012 had a regular pre-proceedings volume published in the book series Lecture Notes in Computer Science:

Barry S. Cooper, Anuj Dawar, and Benedikt Löwe (eds.), How the World Computes, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012, Proceedings, Heidelberg 2012 [Lecture Notes in Computer Science 7318].

As a follow-up to the conference, the organizers of CiE 2012 have also prepared post-conference publications. Two special issues of journals are being edited with journal versions of talks and presentations at CiE 2012. Our publication policy does not allow double publications of the same research content: in order to get accepted for a post-proceedings special issue, a journal version of a talk must exhibit unpublished research content beyond the content printed in the LNCS volume.

This special issue of the journal Logical Methods in Computer Science is one of the post-conference publications. The special issue underwent a thorough and strict refereeing process. After CiE 2012, we invited nine authors to submit a journal version of their paper to this special issue; in the end, we accepted the seven papers that the reader can find in this issue.

The selection procedure was the work of many referees who put in a lot of work to ascertain the quality of the special issue. The paper by Eric Allender, Harry Buhrman, Luke Friedman, and Bruno Loff represents the special session on Cryptography, Complexity, and Randomness (organized by Rod Downey and Jack Lutz) at CiE 2012. The remaining six papers are full versions of contributed talks; all of those have a short version published in the mentioned LNCS pre-proceedings volume.

We would like to thank all our referees for their help in producing this special issue, including the members of the CiE 2012 Programme Committee.

Finally, we would also like to express our gratitude to the many sponsors that made the Turing Centenary Conference possible. They are (in alphabetic order): the Association for Symbolic Logic, Cambridge University Press, Elsevier B.V., the European Association for Computer Science Logic (EACSL), the International Federation for Computational Logic (IFCoLog), IOS Press, the Isaac Newton Institute for Mathematical Sciences, King's College, Cambridge, Microsoft Research Cambridge, Robinson College Cambridge, Science Magazine/AAAS, Springer-Verlag, and the University of Cambridge.

For the most current information about the conference series CiE-CS, we refer the reader to our web-page


Arnold Beckmann, Anuj Dawar
CiE 2012 Guest Editor, CiE 2012 PC co-Chair

Full Text: PDF

Creative Commons