New Computational Paradigms

CiE 2005: New Computational Paradigms illc. uva. nl/CiE/ ThecooperationComputabilityinEurope (CiE)isaninformalEuropeannetwork covering computability in theoretical computer science and mathematical logic, ranging from application of novel approaches to computation to set-theoretic analysesofin?nitarycomputingmodels. Thecooperationconsistsofelevenmain nodesandincludesover400researchers;itiscoordinatedfromLeeds(UK). More information about CiE can be found in Barry Cooper s introductory paper to this volume (p. 1) and at amsta. leeds. ac. uk/pure/staff/cooper/cie. html CiE 2005 was a conference on the special topic New Computational Pa- digms and was held in Amsterdam in June 2005. It was initiated by and served as a focus point for the informal cooperation CiE. The topic of New Com- tational Paradigms covers connections between computation and physical s- tems (e. g. , quantum computation, neural nets, molecular computation) but also higher mathematical models of computation (e. g. , in?nitary computation or real computation). Computability theory is central to large areas of theoretical computer science and mathematical logic. Traditionally, the computational model of the Turing machine (or mathematically equivalent models) has been used to reason about computation or computability. For general computability inquiries (with - bounded resources), the choice of the model of computation hardly matters (this fact is encapsulated in the so-called Church-Turing thesis ); this could change as soon as questions of e?ciency are investigated.

Klappentext

CiE 2005: New Computational Paradigms http://www. illc. uva. nl/CiE/ ThecooperationComputabilityinEurope (CiE)isaninformalEuropeannetwork covering computability in theoretical computer science and mathematical logic, ranging from application of novel approaches to computation to set-theoretic analysesofin?nitarycomputingmodels. Thecooperationconsistsofelevenmain nodesandincludesover400researchers;itiscoordinatedfromLeeds(UK). More information about CiE can be found in Barry Cooper s introductory paper to this volume (p. 1) and at http://www. amsta. leeds. ac. uk/pure/staff/cooper/cie. html CiE 2005 was a conference on the special topic New Computational Pa- digms and was held in Amsterdam in June 2005. It was initiated by and served as a focus point for the informal cooperation CiE. The topic of New Com- tational Paradigms covers connections between computation and physical s- tems (e. g. , quantum computation, neural nets, molecular computation) but also higher mathematical models of computation (e. g. , in?nitary computation or real computation). Computability theory is central to large areas of theoretical computer science and mathematical logic. Traditionally, the computational model of the Turing machine (or mathematically equivalent models) has been used to reason about computation or computability. For general computability inquiries (with - bounded resources), the choice of the model of computation hardly matters (this fact is encapsulated in the so-called Church-Turing thesis ); this could change as soon as questions of e?ciency are investigated.

Inhalt
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 theKorteweg-de Vries Equation.- Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism.