Ebook: New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings

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.

---

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.

Content:
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
Borel Ranks and Wadge Degrees of Context Free ?-Languages....Pages 128-128
Fewer Epistemological Challenges for Connectionism....Pages 129-138
An Algebraic View on Exact Learning from Queries....Pages 139-149
The Church-Turing Thesis: Breaking the Myth....Pages 150-151
Robust Simulations of Turing Machines with Analytic Maps and Flows....Pages 152-168
Infinitary Computability with Infinite Time Turing Machines....Pages 169-179
Combinatorial Models of Gene Assembly....Pages 180-187
Symmetric Enumeration Reducibility....Pages 188-195
Computability-Theoretic and Proof-Theoretic Aspects of Vaughtian Model Theory....Pages 196-208
Finite Trees as Ordinals....Pages 209-210
On the Problems of Definability in the Enumeration Degrees....Pages 211-220
Computing a Model of Set Theory....Pages 221-222
Proof Mining in Functional Analysis....Pages 223-232
Towards Computability of Higher Type Continuous Data....Pages 233-234
The Power of Mobility: Four Membranes Suffice....Pages 235-241
The Small Grzegorczyk Classes and the Typed ?-Calculus....Pages 242-251
The Flow of Data and the Complexity of Algorithms....Pages 252-262
On a Question of Sacks — A Partial Solution on the Positive Side....Pages 263-274
The Low Splitting Theorem in the Difference Hierarchy....Pages 275-286
Geometric Software: Robustness Issues and Model of Computation....Pages 287-296
The Dimension of a Point: Computability Meets Fractal Geometry....Pages 297-298
Accepting Networks of Splicing Processors....Pages 299-299
Hilbert’s Tenth Problem and Paradigms of Computation....Pages 300-309
On Some Relations Between Approximation Problems and PCPs over the Real Numbers....Pages 310-321
Correlation Dimension and the Quality of Forecasts Given by a Neural Network....Pages 322-331
The Computational Complexity of One-Dimensional Sandpiles....Pages 332-341
Categoricity in Restricted Classes....Pages 342-348
Recursion and Complexity....Pages 349-349
FM-Representability and Beyond....Pages 350-357
Formalising Exact Arithmetic in Type Theory....Pages 358-367
Complexity in Predicative Arithmetic....Pages 368-377
Domain-Theoretic Formulation of Linear Boundary Value Problems....Pages 378-384
Membrane Computing: Power, Efficiency, Applications....Pages 385-395
The Analogue of B?chi’s Problem for Polynomials....Pages 396-407
On the Turing Degrees of Divergence Bounded Computable Reals....Pages 408-417
New Algorithmic Paradigms in Exponential Time Algorithms....Pages 418-428
Some Reducibilities on Regular Sets....Pages 429-429
Computability and Discrete Dynamical Systems....Pages 430-439
Uniform Operators....Pages 440-440
Minimal Pairs and Quasi-minimal Degrees for the Joint Spectra of Structures....Pages 441-450
Presentations of K-Trivial Reals and Kolmogorov Complexity....Pages 451-460
Presentations of Structures in Admissible Sets....Pages 461-469
An Environment Aware P-System Model of Quorum Sensing....Pages 470-478
Kripke Models, Distributive Lattices, and Medvedev Degrees....Pages 479-485
Arthur-Merlin Games and the Problem of Isomorphism Testing....Pages 486-494
Beyond the Super-Turing Snare: Analog Computation and Digital Virtuality....Pages 495-506
A Network Model of Analogue Computation over Metric Algebras....Pages 507-514
Computable Analysis....Pages 515-529
The Transfinite Action of 1 Tape Turing Machines....Pages 530-531
Complexity of Continuous Space Machine Operations....Pages 532-539
Computable Analysis of a Non-homogeneous Boundary-Value Problem for the Korteweg-de Vries Equation....Pages 540-551
Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism....Pages 552-561
Back Matter....Pages 562-571
....Pages -