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

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 -