How the World Computes

1. Front Matter

   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

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.

• combinatorial algorithms
• formal methods
• parameterized complexity
• reinforcement learning
• universal machine
• algorithm analysis and problem complexity

• 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

Policies and ethics