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. Front Matter....Pages - Heap-Abstraction for an Object-Oriented Calculus with Thread Classes....Pages 1-10 From Constructibility and Absoluteness to Computability and Domain Independence....Pages 11-20 Datatype-Generic Reasoning....Pages 21-34 The Logical Strength of the Uniform Continuity Theorem....Pages 35-39 Elementary Algebraic Specifications of the Rational Function Field....Pages 40-54 Random Closed Sets....Pages 55-64 Deep Inference and Its Normal Form of Derivations....Pages 65-74 Logspace Complexity of Functions and Structures....Pages 75-84 Prefix-Like Complexities and Computability in the Limit....Pages 85-93 Partial Continuous Functions and Admissible Domain Representations....Pages 94-104 An Invariant Cost Model for the Lambda Calculus....Pages 105-114 On the Complexity of the Sperner Lemma....Pages 115-124 The Church-Turing Thesis: Consensus and Opposition....Pages 125-132 Gödel and the Origins of Computer Science....Pages 133-136 The Role of Algebraic Models and Type-2 Theory of Effectivity in Special Purpose Processor Design....Pages 137-146 Turing Universality in Dynamical Systems....Pages 147-152 Every Sequence Is Decompressible from a Random One....Pages 153-162 Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal....Pages 163-172 LJQ: A Strongly Focused Calculus for Intuitionistic Logic....Pages 173-185 Böhm Trees, Krivine’s Machine and the Taylor Expansion of Lambda-Terms....Pages 186-197 What Does the Incompleteness Theorem Add to the Unsolvability of the Halting Problem?....Pages 198-198 An Analysis of the Lemmas of Urysohn and Urysohn-Tietze According to Effective Borel Measurability....Pages 199-208 Enumeration Reducibility with Polynomial Time Bounds....Pages 209-220 Coinductive Proofs for Basic Real Computation....Pages 221-230 A Measure of Space for Computing over the Reals....Pages 231-240 On Graph Isomorphism for Restricted Graph Classes....Pages 241-256 Infinite Time Register Machines....Pages 257-266 Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Hybrid Systems....Pages 267-276 Forcing with Random Variables and Proof Complexity....Pages 277-278 Complexity-Theoretic Hierarchies....Pages 279-288 Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests....Pages 289-296 Lower Bounds Using Kolmogorov Complexity....Pages 297-306 The Jump Classes of Minimal Covers....Pages 307-318 Space Bounds for Infinitary Computation....Pages 319-329 From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials....Pages 330-341 Towards a Trichotomy for Quantified H -Coloring....Pages 342-352 Two Open Problems on Effective Dimension....Pages 353-359 Optimization and Approximation Problems Related to Polynomial System Solving....Pages 360-367 Uncomputability Below the Real Halting Problem....Pages 368-377 Constraints on Hypercomputation....Pages 378-387 Martingale Families and Dimension in P....Pages 388-397 Can General Relativistic Computers Break the Turing Barrier?....Pages 398-412 Degrees of Weakly Computable Reals....Pages 413-422 Understanding and Using Spector’s Bar Recursive Interpretation of Classical Analysis....Pages 423-434 A Subrecursive Refinement of the Fundamental Theorem of Algebra....Pages 435-444 An Introduction to Program and Thread Algebra....Pages 445-458 Fast Quantifier Elimination Means P = NP....Pages 459-470 Admissible Representations in Computable Analysis....Pages 471-480 Do Noetherian Modules Have Noetherian Basis Functions?....Pages 481-489 Inverting Monotone Continuous Functions in Constructive Analysis....Pages 490-504 Partial Recursive Functions in Martin-Löf Type Theory....Pages 505-515 Partially Ordered Connectives and ∑ 1 1 on Finite Models....Pages 516-525 Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes....Pages 526-535 Gödel’s Conflicting Approaches to Effective Calculability....Pages 536-537 Co-total Enumeration Degrees....Pages 538-545 Relativized Degree Spectra....Pages 546-555 Phase Transition Thresholds for Some Natural Subclasses of the Computable Functions....Pages 556-570 Non-deterministic Halting Times for Hamkins-Kidder Turing Machines....Pages 571-574 Kurt Gödel and Computability Theory....Pages 575-583 A Computability Theory of Real Numbers....Pages 584-594 Primitive Recursive Selection Functions over Abstract Algebras....Pages 595-606 Back Matter....Pages - 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.