Logical Approaches to Computational Barriers: Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings (Lecture Notes in Computer Science (3988))

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. Frontmatter Heap-Abstraction for an Object-Oriented Calculus with Thread Classes From Constructibility and Absoluteness to Computability and Domain Independence Datatype-Generic Reasoning The Logical Strength of the Uniform Continuity Theorem Elementary Algebraic Specifications of the Rational Function Field Random Closed Sets Deep Inference and Its Normal Form of Derivations Logspace Complexity of Functions and Structures Prefix-Like Complexities and Computability in the Limit Partial Continuous Functions and Admissible Domain Representations An Invariant Cost Model for the Lambda Calculus On the Complexity of the Sperner Lemma The Church-Turing Thesis: Consensus and Opposition G\"{o}del and the Origins of Computer Science The Role of Algebraic Models and Type-2 Theory of Effectivity in Special Purpose Processor Design Turing Universality in Dynamical Systems Every Sequence Is Decompressible from a Random One Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal LJQ: A Strongly Focused Calculus for Intuitionistic Logic B\"{o}hm Trees, Krivine's Machine and the Taylor Expansion of Lambda-Terms What Does the Incompleteness Theorem Add to the Unsolvability of the Halting Problem? An Analysis of the Lemmas of Urysohn and Urysohn-Tietze According to Effective Borel Measurability Enumeration Reducibility with Polynomial Time Bounds Coinductive Proofs for Basic Real Computation A Measure of Space for Computing over the Reals On Graph Isomorphism for Restricted Graph Classes Infinite Time Register Machines Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Hybrid Systems Forcing with Random Variables and Proof Complexity Complexity-Theoretic Hierarchies Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests Lower Bounds Using Kolmogorov Complexity The Jump Classes of Minimal Covers Space Bounds for Infinitary Computation From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials Towards a Trichotomy for Quantified {\itshape H}-Coloring Two Open Problems on Effective Dimension Optimization and Approximation Problems Related to Polynomial System Solving Uncomputability Below the Real Halting Problem Constraints on Hypercomputation Martingale Families and Dimension in P Can General Relativistic Computers Break the Turing Barrier? Degrees of Weakly Computable Reals Understanding and Using Spector's Bar Recursive Interpretation of Classical Analysis A Subrecursive Refinement of the Fundamental Theorem of Algebra An Introduction to Program and Thread Algebra Fast Quantifier Elimination Means P = NP Admissible Representations in Computable Analysis Do Noetherian Modules Have Noetherian Basis Functions? Inverting Monotone Continuous Functions in Constructive Analysis Partial Recursive Functions in Martin-L\"{o}f Type Theory Partially Ordered Connectives and $\sum$ 1 1 on Finite Models Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes G\"{o}del's Conflicting Approaches to Effective Calculability Co-total Enumeration Degrees Relativized Degree Spectra Phase Transition Thresholds for Some Natural Subclasses of the Computable Functions Non-deterministic Halting Times for Hamkins-Kidder Turing Machines Kurt G\"{o}del and Computability Theory A Computability Theory of Real Numbers Primitive Recursive Selection Functions over Abstract Algebras Backmatter Constitutes the refereed proceedings of the Second International Conference on Computability in Europe, CiE 2006, held in Swansea, UK, June/July 2006. This book covers proofs and computation, computable analysis, challenges in complexity, foundations of programming, and mathematical models of computers and hypercomputers.