Logical Approaches to Computational Barriers

1. Front Matter

   PDF

2. Heap-Abstraction for an Object-Oriented Calculus with Thread Classes

   • Erika Ábrahám, Andreas Grüner, Martin Steffen

   Pages 1-10

3. From Constructibility and Absoluteness to Computability and Domain Independence

   • Arnon Avron

   Pages 11-20

4. Datatype-Generic Reasoning

   • Roland Backhouse

   Pages 21-34

5. The Logical Strength of the Uniform Continuity Theorem

   • Josef Berger

   Pages 35-39

6. Elementary Algebraic Specifications of the Rational Function Field

   • J. A. Bergstra

   Pages 40-54

7. Random Closed Sets

   • Paul Brodhead, Douglas Cenzer, Seyyed Dashti

   Pages 55-64

8. Deep Inference and Its Normal Form of Derivations

   • Kai Brünnler

   Pages 65-74

9. Logspace Complexity of Functions and Structures

   • Douglas Cenzer, Zia Uddin

   Pages 75-84

10. Prefix-Like Complexities and Computability in the Limit

    • Alexey Chernov, Jürgen Schmidhuber

    Pages 85-93

11. Partial Continuous Functions and Admissible Domain Representations

    • Fredrik Dahlgren

    Pages 94-104

12. An Invariant Cost Model for the Lambda Calculus

    • Ugo Dal Lago, Simone Martini

    Pages 105-114

13. On the Complexity of the Sperner Lemma

    • Stefan Dantchev

    Pages 115-124

14. The Church-Turing Thesis: Consensus and Opposition

    • Martin Davis

    Pages 125-132

15. Gödel and the Origins of Computer Science

    • John W. Dawson Jr.

    Pages 133-136

16. The Role of Algebraic Models and Type-2 Theory of Effectivity in Special Purpose Processor Design

    • Gregorio de Miguel Casado, Juan Manuel García Chamizo

    Pages 137-146

17. Turing Universality in Dynamical Systems

    • Jean-Charles Delvenne

    Pages 147-152

18. Every Sequence Is Decompressible from a Random One

    • David Doty

    Pages 153-162

19. Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal

    • Jérôme Durand-Lose

    Pages 163-172

20. LJQ: A Strongly Focused Calculus for Intuitionistic Logic

    • Roy Dyckhoff, Stéphane Lengrand

    Pages 173-185

CiE 2006: Logical Approaches to Computational Barriers Swansea, Wales, June 30 - July 5, 2006 Computability in Europe (CiE) is an informal network of European scientists working on computability theory, including its foundations, technical devel- ment, and applications. Among the aims of the network is to advance our t- oretical understanding of what can and cannot be computed, by any means of computation. Its scienti?c vision is broad: computations may be performed with discrete or continuous data by all kinds of algorithms, programs, and - chines. Computations may be made by experimenting with any sort of physical system obeying the laws of a physical theory such as Newtonian mechanics, quantum theory or relativity. Computations may be very general, depending upon the foundations of set theory; or very speci?c, using the combinatorics of ?nite structures. CiE also works on subjects intimately related to computation, especially theories of data and information, and methods for formal reasoning about computations. The sources of new ideas and methods include practical developments in areas such as neural networks, quantum computation, natural computation, molecular computation, and computational learning. Applications are everywhere, especially, in algebra, analysis and geometry, or data types and programming. This volume, Logical Approaches to Computational Barriers, is the proce- ings of the second in a series of conferences of CiE that was held at the Depa- ment of Computer Science, Swansea University, 30 June - 5 July, 2006.

• algorithms
• bioinformatics
• calculus
• classical computability
• complexity
• computability theory
• computable structures
• computational learning
• computational logic
• computational modeling
• constructive mathematics
• logic
• methodol
• optimization
• programming
• algorithm analysis and problem complexity

• Department of Computer Science, Swansea University, Swansea, United Kingdom

  Arnold Beckmann

• Department of Computer Science, University of Wales Swansea, Swansea, UK

  Ulrich Berger

• Universiteit van Amsterdam, Amsterdam, The Netherlands

  Benedikt Löwe

• School of Physical Sciences, Swansea University, Swansea, United Kingdom

  John V. Tucker

Policies and ethics