New Computational Paradigms: First Conference on Computability in Europe, Cie 2005, Amsterdam, the Netherlands, June 8-12, 2005, Proceedings

ISBN-13: 9783540261797 / Angielski / Miękka / 2005 / 578 str.

Barry S. Cooper; Benedikt Lowe

Opis

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.

Spis treści

Introduction: If CiE Did Not Exist, It Would Be Necessary to Invent It.- Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees.- The Fan Theorem and Uniform Continuity.- Continuous Semantics for Strong Normalization.- A Thread Algebra with Multi-level Strategic Interleaving.- Membrane Computing — Current Results and Future Problems.- How to Compare the Power of Computational Models.- Recombinant DNA ,Gene Splicing as Generative Devices of Formal Languages.- Quantum Computing.- Symbol Grounding in Connectionist and Adaptive Agent Models.- The Complexity of Inductive Definability.- A Logical Approach to Abstract Algebra.- Schnorr Dimension.- Abstract Geometrical Computation: Turing-Computing Ability and Undecidability.- Computability in Computational Geometry.- Shrad: A Language for Sequential Real Number Computation.- Borel Ranks and Wadge Degrees of Context Free ?-Languages.- Fewer Epistemological Challenges for Connectionism.- An Algebraic View on Exact Learning from Queries.- The Church-Turing Thesis: Breaking the Myth.- Robust Simulations of Turing Machines with Analytic Maps and Flows.- Infinitary Computability with Infinite Time Turing Machines.- Combinatorial Models of Gene Assembly.- Symmetric Enumeration Reducibility.- Computability-Theoretic and Proof-Theoretic Aspects of Vaughtian Model Theory.- Finite Trees as Ordinals.- On the Problems of Definability in the Enumeration Degrees.- Computing a Model of Set Theory.- Proof Mining in Functional Analysis.- Towards Computability of Higher Type Continuous Data.- The Power of Mobility: Four Membranes Suffice.- The Small Grzegorczyk Classes and the Typed ?-Calculus.- The Flow of Data and the Complexity of Algorithms.- On a Question of Sacks — A Partial Solution on the Positive Side.- The Low Splitting Theorem in the Difference Hierarchy.- Geometric Software: Robustness Issues and Model of Computation.- The Dimension of a Point: Computability Meets Fractal Geometry.- Accepting Networks of Splicing Processors.- Hilbert’s Tenth Problem and Paradigms of Computation.- On Some Relations Between Approximation Problems and PCPs over the Real Numbers.- Correlation Dimension and the Quality of Forecasts Given by a Neural Network.- The Computational Complexity of One-Dimensional Sandpiles.- Categoricity in Restricted Classes.- Recursion and Complexity.- FM-Representability and Beyond.- Formalising Exact Arithmetic in Type Theory.- Complexity in Predicative Arithmetic.- Domain-Theoretic Formulation of Linear Boundary Value Problems.- Membrane Computing: Power, Efficiency, Applications.- The Analogue of Büchi’s Problem for Polynomials.- On the Turing Degrees of Divergence Bounded Computable Reals.- New Algorithmic Paradigms in Exponential Time Algorithms.- Some Reducibilities on Regular Sets.- Computability and Discrete Dynamical Systems.- Uniform Operators.- Minimal Pairs and Quasi-minimal Degrees for the Joint Spectra of Structures.- Presentations of K-Trivial Reals and Kolmogorov Complexity.- Presentations of Structures in Admissible Sets.- An Environment Aware P-System Model of Quorum Sensing.- Kripke Models, Distributive Lattices, and Medvedev Degrees.- Arthur-Merlin Games and the Problem of Isomorphism Testing.- Beyond the Super-Turing Snare: Analog Computation and Digital Virtuality.- A Network Model of Analogue Computation over Metric Algebras.- Computable Analysis.- The Transfinite Action of 1 Tape Turing Machines.- Complexity of Continuous Space Machine Operations.- Computable Analysis of a Non-homogeneous Boundary-Value Problem for the Korteweg-de Vries Equation.- Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism.