Logical Approaches to Computational Barriers: Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings

Erika Ábrahám, Andreas Grüner (auth.), Arnold Beckmann, Ulrich Berger, Benedikt Löwe, John V. Tucker (eds.)3540354662, 9783540354666

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.

---

Table of contents :
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 –