Skip to main content
SpringerLink
Log in
Book cover

How the World Computes

Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012, Proceedings

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. S. Barry Cooper

    1. School of Mathematics, University of Leeds, Leeds, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Anuj Dawar

    1. Computer Laboratory, University of Cambridge, Cambridge, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Benedikt Löwe

    1. Institute for Logic, Language and Computation, University of Amsterdam, Amsterdam, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast track conference proceedings
  • Unique visibility
  • State of the art research

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 7318)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: CiE 2012.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (75 papers)

  1. Front Matter

    Download chapter PDF

  2. Ordinal Analysis and the Infinite Ramsey Theorem

    • Bahareh Afshari, Michael Rathjen
    Pages 1-10

  3. Curiouser and Curiouser: The Link between Incompressibility and Complexity

    • Eric Allender
    Pages 11-16

  4. Information and Logical Discrimination

    • Patrick Allo
    Pages 17-28

  5. Robustness of Logical Depth

    • Luís Antunes, Andre Souto, Andreia Teixeira
    Pages 29-34

  6. Turing’s Normal Numbers: Towards Randomness

    • Verónica Becher
    Pages 35-45

  7. Logic of Ruler and Compass Constructions

    • Michael Beeson
    Pages 46-55

  8. On the Computational Content of the Brouwer Fixed Point Theorem

    • Vasco Brattka, Stéphane Le Roux, Arno Pauly
    Pages 56-67

  9. Square Roots and Powers in Constructive Banach Algebra Theory

    • Douglas S. Bridges, Robin S. Havea
    Pages 68-77

  10. The Mate-in-n Problem of Infinite Chess Is Decidable

    • Dan Brumleve, Joel David Hamkins, Philipp Schlicht
    Pages 78-88

  11. A Note on Ramsey Theorems and Turing Jumps

    • Lorenzo Carlucci, Konrad Zdanowski
    Pages 89-95

  12. Automatic Functions, Linear Time and Learning

    • John Case, Sanjay Jain, Samuel Seah, Frank Stephan
    Pages 96-106

  13. An Undecidable Nested Recurrence Relation

    • Marcel Celaya, Frank Ruskey
    Pages 107-117

  14. Hard Instances of Algorithms and Proof Systems

    • Yijia Chen, Jörg Flum, Moritz Müller
    Pages 118-128

  15. On Mathias Generic Sets

    • Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst
    Pages 129-138

  16. Complexity of Deep Inference via Atomic Flows

    • Anupam Das
    Pages 139-150

  17. Connecting Partial Words and Regular Languages

    • Jürgen Dassow, Florin Manea, Robert Mercaş
    Pages 151-161

  18. Randomness, Computation and Mathematics

    • Rod Downey
    Pages 162-181

  19. Learning, Social Intelligence and the Turing Test

    • Bruce Edmonds, Carlos Gershenson
    Pages 182-192

  20. Confluence in Data Reduction: Bridging Graph Transformation and Kernelization

    • Hartmut Ehrig, Claudia Ermel, Falk Hüffner, Rolf Niedermeier, Olga Runge
    Pages 193-202
Back to top

Other volumes

  1. How the World Computes

Keywords

About this book

This book constitutes the refereed proceedings of the Turing Centenary Conference and the 8th Conference on Computability in Europe, CiE 2012, held in Cambridge, UK, in June 2012.
The 53 revised papers presented together with 6 invited lectures were carefully reviewed and selected with an acceptance rate of under 29,8%. The CiE 2012 Turing Centenary Conference will be remembered as a historic event in the continuing development of the powerful explanatory role of computability across a wide spectrum of research areas. The papers presented at CiE 2012 represent the best of current research in the area, and forms a fitting tribute to the short but brilliant trajectory of Alan Mathison Turing. Both the conference series and the association promote the development of computability-related science, ranging over mathematics, computer science and applications in various natural and engineering sciences such as physics and biology, and also including the promotion of related non-scientific fields such as philosophy and history of computing.

Editors and Affiliations

  • School of Mathematics, University of Leeds, Leeds, UK

    S. Barry Cooper

  • Computer Laboratory, University of Cambridge, Cambridge, UK

    Anuj Dawar

  • Institute for Logic, Language and Computation, University of Amsterdam, Amsterdam, The Netherlands

    Benedikt Löwe

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation