This book constitutes the refereed proceedings of the first International Conference on Computability in Europe, CiE 2005, held in Amsterdam, The Netherlands in June 2005.
The 68 revised full papers presented were carefully reviewed and selected from 144 submissions. Among them are papers corresponding to two tutorials, six plenary talks and papers of six special sessions involving mathematical logic and computer science at the same time as offering the methodological foundations for models of computation. The papers address many aspects of computability in Europe with a special focus on new computational paradigms. These include first of all connections between computation and physical systems (e.g., quantum and analog computation, neural nets, molecular computation), but also cover new perspectives on models of computation arising from basic research in mathematical logic and theoretical computer science.
Author(s): S. Barry Cooper (auth.), S. Barry Cooper, Benedikt Löwe, Leen Torenvliet (eds.)
Series: Lecture Notes in Computer Science 3526 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 578
Tags: Theory of Computation; Algorithm Analysis and Problem Complexity; Mathematics of Computing; Computing Methodologies; Bioinformatics; Algorithms
Front Matter....Pages -
Introduction: If CiE Did Not Exist, It Would Be Necessary to Invent It....Pages 1-7
Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees....Pages 8-17
The Fan Theorem and Uniform Continuity....Pages 18-22
Continuous Semantics for Strong Normalization....Pages 23-34
A Thread Algebra with Multi-level Strategic Interleaving....Pages 35-48
Membrane Computing — Current Results and Future Problems....Pages 49-53
How to Compare the Power of Computational Models....Pages 54-64
Recombinant DNA ,Gene Splicing as Generative Devices of Formal Languages....Pages 65-67
Quantum Computing....Pages 68-68
Symbol Grounding in Connectionist and Adaptive Agent Models....Pages 69-74
The Complexity of Inductive Definability....Pages 75-85
A Logical Approach to Abstract Algebra....Pages 86-95
Schnorr Dimension....Pages 96-105
Abstract Geometrical Computation: Turing-Computing Ability and Undecidability....Pages 106-116
Computability in Computational Geometry....Pages 117-127
Shrad : A Language for Sequential Real Number Computation....Pages 128-128
Borel Ranks and Wadge Degrees of Context Free ω -Languages....Pages 129-138
Fewer Epistemological Challenges for Connectionism....Pages 139-149
An Algebraic View on Exact Learning from Queries....Pages 150-151
The Church-Turing Thesis: Breaking the Myth....Pages 152-168
Robust Simulations of Turing Machines with Analytic Maps and Flows....Pages 169-179
Infinitary Computability with Infinite Time Turing Machines....Pages 180-187
Combinatorial Models of Gene Assembly....Pages 188-195
Symmetric Enumeration Reducibility....Pages 196-208
Computability-Theoretic and Proof-Theoretic Aspects of Vaughtian Model Theory....Pages 209-210
Finite Trees as Ordinals....Pages 211-220
On the Problems of Definability in the Enumeration Degrees....Pages 221-222
Computing a Model of Set Theory....Pages 223-232
Proof Mining in Functional Analysis....Pages 233-234
Towards Computability of Higher Type Continuous Data....Pages 235-241
The Power of Mobility: Four Membranes Suffice....Pages 242-251
The Small Grzegorczyk Classes and the Typed λ -Calculus....Pages 252-262
The Flow of Data and the Complexity of Algorithms....Pages 263-274
On a Question of Sacks — A Partial Solution on the Positive Side....Pages 275-286
The Low Splitting Theorem in the Difference Hierarchy....Pages 287-296
Geometric Software: Robustness Issues and Model of Computation....Pages 297-298
The Dimension of a Point: Computability Meets Fractal Geometry....Pages 299-299
Accepting Networks of Splicing Processors....Pages 300-309
Hilbert’s Tenth Problem and Paradigms of Computation....Pages 310-321
On Some Relations Between Approximation Problems and PCPs over the Real Numbers....Pages 322-331
Correlation Dimension and the Quality of Forecasts Given by a Neural Network....Pages 332-341
The Computational Complexity of One-Dimensional Sandpiles....Pages 342-348
Categoricity in Restricted Classes....Pages 349-349
Recursion and Complexity....Pages 350-357
FM-Representability and Beyond....Pages 358-367
Formalising Exact Arithmetic in Type Theory....Pages 368-377
Complexity in Predicative Arithmetic....Pages 378-384
Domain-Theoretic Formulation of Linear Boundary Value Problems....Pages 385-395
Membrane Computing: Power, Efficiency, Applications....Pages 396-407
The Analogue of Büchi’s Problem for Polynomials....Pages 408-417
On the Turing Degrees of Divergence Bounded Computable Reals....Pages 418-428
New Algorithmic Paradigms in Exponential Time Algorithms....Pages 429-429
Some Reducibilities on Regular Sets....Pages 430-439
Computability and Discrete Dynamical Systems....Pages 440-440
Uniform Operators....Pages 441-450
Minimal Pairs and Quasi-minimal Degrees for the Joint Spectra of Structures....Pages 451-460
Presentations of K -Trivial Reals and Kolmogorov Complexity....Pages 461-469
Presentations of Structures in Admissible Sets....Pages 470-478
An Environment Aware P-System Model of Quorum Sensing....Pages 479-485
Kripke Models, Distributive Lattices, and Medvedev Degrees....Pages 486-494
Arthur-Merlin Games and the Problem of Isomorphism Testing....Pages 495-506
Beyond the Super-Turing Snare: Analog Computation and Digital Virtuality....Pages 507-514
A Network Model of Analogue Computation over Metric Algebras....Pages 515-529
Computable Analysis....Pages 530-531
The Transfinite Action of 1 Tape Turing Machines....Pages 532-539
Complexity of Continuous Space Machine Operations....Pages 540-551
Computable Analysis of a Non-homogeneous Boundary-Value Problem for the Korteweg-de Vries Equation....Pages 552-561
Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism....Pages 562-571
Back Matter....Pages -
