Mathematical Theory And Computational Practice: 5th Conference On Computability In Europe, Cie 2009, Heidelberg, Germany, July 19-24, 2009, Proceedings (lecture Notes In Computer Science)

This book constitutes the proceedings of the 5th Conference on Computability in Europe, CiE 2009, held in Heidelberg, Germany, during July 19-24, 2009. The 34 papers presented together with 17 invited lectures were carefully reviewed and selected from 100 submissions. The aims of the conference is to advance our theoretical understanding of what can and cannot be computed, by any means of computation. It is the largest international meeting focused on computability theoretic issues. Front Matter....Pages - First-Order Universality for Real Programs....Pages 1-10 Skolem + Tetration Is Well-Ordered....Pages 11-20 Structures of Some Strong Reducibilities....Pages 21-30 Complexity of Existential Positive First-Order Logic....Pages 31-36 Stochastic Programs and Hybrid Automata for (Biological) Modeling....Pages 37-48 Numberings and Randomness....Pages 49-58 The Strength of the Grätzer-Schmidt Theorem....Pages 59-67 Hyperloops Do Not Threaten the Notion of an Effective Procedure....Pages 68-78 Minimum Entropy Combinatorial Optimization Problems....Pages 79-88 Program Self-reference in Constructive Scott Subdomains....Pages 89-98 $\Sigma^0_1$ and $\Pi^0_1$ Equivalence Structures....Pages 99-108 Immunity for Closed Sets....Pages 109-117 Lower Bounds for Kernelizations and Other Preprocessing Procedures....Pages 118-128 Infinite-Time Turing Machines and Borel Reducibility....Pages 129-133 Cutting Planes and the Parameter Cutwidth....Pages 134-143 Members of Random Closed Sets....Pages 144-153 Lowness for Demuth Randomness....Pages 154-166 Graph States and the Necessity of Euler Decomposition....Pages 167-177 On Stateless Multicounter Machines....Pages 178-187 Computability of Continuous Solutions of Higher-Type Equations....Pages 188-197 Equivalence Relations on Classes of Computable Structures....Pages 198-207 Fractals Generated by Algorithmically Random Brownian Motion....Pages 208-217 Computable Exchangeable Sequences Have Computable de Finetti Measures....Pages 218-231 Spectra of Algebraic Fields and Subfields....Pages 232-241 Definability in the Local Theory of the ω -Enumeration Degrees....Pages 242-249 Computability of Analytic Functions with Analytic Machines....Pages 250-259 An Application of Martin-Löf Randomness to Effective Probability Theory....Pages 260-269 Index Sets and Universal Numberings....Pages 270-279 Ordinal Computability....Pages 280-289 A Gandy Theorem for Abstract Structures and Applications to First-Order Definability....Pages 290-299 Constructing New Aperiodic Self-simulating Tile Sets....Pages 300-309 Relationship between Kanamori-McAloon Principle and Paris-Harrington Theorem....Pages 310-323 The First Order Theories of the Medvedev and Muchnik Lattices....Pages 324-331 Infima of d . r . e . Degrees....Pages 332-341 A Divergence Formula for Randomness and Dimension....Pages 342-351 On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants....Pages 352-361 0 ′′ -Categorical Completely Decomposable Torsion-Free Abelian Groups....Pages 362-371 Notes on the Jump of a Structure....Pages 372-378 A General Representation Theorem for Probability Functions Satisfying Spectrum Exchangeability....Pages 379-388 Stability under Strategy Switching....Pages 389-398 Computational Heuristics for Simplifying a Biological Model....Pages 399-408 Functions Definable by Arithmetic Circuits....Pages 409-418 Survey on Oblivious Routing Strategies....Pages 419-429 An Approach to the Engineering of Cellular Models Based on P Systems....Pages 430-436 Decidability of Sub-theories of Polynomials over a Finite Field....Pages 437-446 Chaitin Ω Numbers and Halting Problems....Pages 447-456 Bayesian Data Integration and Enrichment Analysis for Predicting Gene Function in Malaria....Pages 457-466 Dialectica Interpretation with Fine Computational Control....Pages 467-477 Algorithmic Minimal Sufficient Statistic Revisited....Pages 478-487 A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets....Pages 488-498 On Generating Independent Random Strings....Pages 499-508 Back Matter....Pages -