Logical Approaches to Computational Barriers

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.

Inhalt
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ö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ö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 theHomomorphic 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 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öf Type Theory.- Partially Ordered Connectives and ?1 1 on Finite Models.- Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes.- Gö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ödel and Computability Theory.- A Computability Theory of Real Numbers.- Primitive Recursive Selection Functions over Abstract Algebras.