| Description |
1 online resource |
| Series |
Lecture notes in computer science, 0302-9743 ; 7318 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7318.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
880-01 Ordinal Analysis and the Infinite Ramsey Theorem / Bahareh Afshari and Michael Rathjen -- Curiouser and Curiouser: The Link between Incompressibility and Complexity / Eric Allender -- Information and Logical Discrimination / Patrick Allo -- Robustness of Logical Depth / Luís Antunes, Andre Souto and Andreia Teixeira -- Turing's Normal Numbers: Towards Randomness / Verónica Becher -- Logic of Ruler and Compass Constructions / Michael Beeson -- On the Computational Content of the Brouwer Fixed Point Theorem / Vasco Brattka, Stéphane Le Roux and Arno Pauly -- Square Roots and Powers in Constructive Banach Algebra Theory / Douglas S. Bridges and Robin S. Havea -- The Mate-in-n Problem of Infinite Chess Is Decidable / Dan Brumleve, Joel David Hamkins and Philipp Schlicht -- A Note on Ramsey Theorems and Turing Jumps / Lorenzo Carlucci and Konrad Zdanowski -- Automatic Functions, Linear Time and Learning / John Case, Sanjay Jain, Samuel Seah and Frank Stephan -- An Undecidable Nested Recurrence Relation / Marcel Celaya and Frank Ruskey -- Hard Instances of Algorithms and Proof Systems / Yijia Chen, Jörg Flum and Moritz Müller -- On Mathias Generic Sets / Peter A. Cholak, Damir D. Dzhafarov and Jeffry L. Hirst -- Complexity of Deep Inference via Atomic Flows / Anupam Das -- Connecting Partial Words and Regular Languages / Jürgen Dassow, Florin Manea and Robert Mercaş |
|
880-01/(S Lower Bound on Weights of Large Degree Threshold Functions / Vladimir V. Podolskii -- What Are Computers (If They're not Thinking Things)? / John Preston -- Compactness and the Effectivity of Uniformization / Robert Rettinger -- On the Computability Power of Membrane Systems with Controlled Mobility / Shankara Narayanan Krishna, Bogdan Aman and Gabriel Ciobanu -- On Shift Spaces with Algebraic Structure / Ville Salo and Ilkka Törmä -- Finite State Verifiers with Constant Randomness / A.C. Cem Say and Abuzer Yakaryılmaz -- Game Arguments in Computability Theory and Algorithmic Information Theory / Alexander Shen -- Turing Patterns in Deserts / Jonathan A. Sherratt -- Subsymbolic Computation Theory for the Human Intuitive Processor / Paul Smolensky -- A Correspondence Principle for Exact Constructive Dimension / Ludwig Staiger -- Lown Boolean Subalgebras / Rebecca M. Steiner -- Bringing Up Turing's 'Child-Machine' / Susan G. Sterrett -- Is Turing's Thesis the Consequence of a More General Physical Principle? / Matthew P. Szudzik -- Some Natural Zero One Laws for Ordinals Below ε0 / Andreas Weiermann and Alan R. Woods -- On the Road to Thinking Machines: Insights and Ideas / Jiří Wiedermann -- Making Solomonoff Induction Effective / Or: You Can Learn What You Can Bound / Jörg Zimmermann and Armin B. Cremers |
|
Randomness, Computation and Mathematics / Rod Downey -- Learning, Social Intelligence and the Turing Test / Why an "Out-of-the-Box" Turing Machine Will Not Pass the Turing Test / Bruce Edmonds and Carlos Gershenson -- Confluence in Data Reduction: Bridging Graph Transformation and Kernelization / Hartmut Ehrig, Claudia Ermel, Falk Hüffner, Rolf Niedermeier and Olga Runge -- Highness and Local Noncappability / Chengling Fang, Wang Shenling and Guohua Wu -- Turing Progressions and Their Well-Orders / David Fernández Duque and Joost J. Joosten -- A Short Note on Spector's Proof of Consistency of Analysis / Fernando Ferreira -- Sets of Signals, Information Flow, and Folktales / Mark Alan Finlayson -- On the Foundations and Philosophy of Info-metrics / Amos Golan -- On Mathematicians Who Liked Logic / The Case of Max Newman / Ivor Grattan-Guinness -- Densities and Entropies in Cellular Automata / Pierre Guillon and Charalampos Zinoviadis -- Foundational Analyses of Computation / Yuri Gurevich -- Turing Machine-Inspired Computer Science Results / Juris Hartmanis -- NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs / Sepp Hartung and André Nichterlein -- A Direct Proof of Wiener's Theorem / Matthew Hendtlass and Peter Schuster -- Effective Strong Nullness and Effectively Closed Sets / Kojiro Higuchi and Takayuki Kihara |
|
Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable / Martin Huschenbett -- On the Relative Succinctness of Two Extensions by Definitions of Multimodal Logic / Wiebe van der Hoek, Petar Iliev and Barteld Kooi -- On Immortal Configurations in Turing Machines / Emmanuel Jeandel -- A Slime Mold Solver for Linear Programming Problems / Anders Johannson and James Zou -- Multi-scale Modeling of Gene Regulation of Morphogenesis / Jaap A. Kaandorp, Daniel Botman, Carlos Tamulonis and Roland Dries -- Tree-Automatic Well-Founded Trees / Alexander Kartzow, Jiamou Liu and Markus Lohrey -- Infinite Games and Transfinite Recursion of Multiple Inductive Definitions / Keisuke Yoshii and Kazuyuki Tanaka -- A Hierarchy of Immunity and Density for Sets of Reals / Takayuki Kihara -- How Much Randomness Is Needed for Statistics? / Bjørn Kjos-Hanssen, Antoine Taveneaux and Neil Thapen -- Towards a Theory of Infinite Time Blum-Shub-Smale Machines / Peter Koepke and Benjamin Seyfferth -- Turing Pattern Formation without Diffusion / Shigeru Kondo -- Degrees of Total Algorithms versus Degrees of Honest Functions / Lars Kristiansen -- A 5n -- o(n) Lower Bound on the Circuit Size over U2 of a Linear Boolean Function / Alexander S. Kulikov, Olga Melanich and Ivan Mihajlin -- Local Induction and Provably Total Computable Functions: A Case Study / Andrés Cordón-Franco and F. Félix Lara-Martín |
|
What is Turing's Comparison between Mechanism and Writing Worth? / Jean Lassègue and Giuseppe Longo -- Substitutions and Strongly Deterministic Tilesets / Bastien Le Gloannec and Nicolas Ollinger -- The Computing Spacetime / Fotini Markopoulou -- Unifiability and Admissibility in Finite Algebras / George Metcalfe and Christoph Röthlisberger -- Natural Signs / Ruth Garrett Millikan -- Characteristics of Minimal Effective Programming Systems / Samuel E. Moelius III -- After Turing: Mathematical Modelling in the Biomedical and Social Sciences / From Animal Coat Patterns to Brain Tumours to Saving Marriages / James D. Murray -- Existence of Faster than Light Signals Implies Hypercomputation already in Special Relativity / Péter Németi and Gergely Székely -- Turing Computable Embeddings and Coding Families of Sets / Víctor A. Ocasio-González -- On the Behavior of Tile Assembly System at High Temperatures / Shinnosuke Seki and Yasushi Okuno -- Abstract Partial Cylindrical Algebraic Decomposition I: The Lifting Phase / Grant Olney Passmore and Paul B. Jackson -- Multi-valued Functions in Computability Theory / Arno Pauly -- Relative Randomness for Martin-Löf Random Sets / NingNing Peng, Kojiro Higuchi, Takeshi Yamazaki and Kazuyuki Tanaka -- On the Tarski-Lindenbaum Algebra of the Class of all Strongly Constructivizable Prime Models / Mikhail G. Peretyat'kin |
| Summary |
Annotation This book constitutes the refereed proceedings of the Turing Centenary Conference and the 8th Conference on Computability in Europe, CiE 2012, held in Cambridge, UK, in June 2012. The 53 revised papers presented together with 6 invited lectures were carefully reviewed and selected with an acceptance rate of under 29,8%. The CiE 2012 Turing Centenary Conference will be remembered as a historic event in the continuing development of the powerful explanatory role of computability across a wide spectrum of research areas. The papers presented at CiE 2012 represent the best of current research in the area, and forms a fitting tribute to the short but brilliant trajectory of Alan Mathison Turing. Both the conference series and the association promote the development of computability-related science, ranging over mathematics, computer science and applications in various natural and engineering sciences such as physics and biology, and also including the promotion of related non-scientific fields such as philosophy and history of computing |
| Analysis |
Computer science |
|
Computer software |
|
Computational complexity |
|
Algebra -- Data processing |
|
Logic, Symbolic and mathematical |
|
Computation by Abstract Devices |
|
Algorithm Analysis and Problem Complexity |
|
Discrete Mathematics in Computer Science |
|
Symbolic and Algebraic Manipulation |
|
Mathematical Logic and Foundations |
| Bibliography |
Includes bibliographical references and author index |
| Subject |
Computable functions -- Congresses
|
|
Computer science -- Mathematics -- Congresses
|
|
Informatique.
|
|
Computable functions
|
|
Computer science -- Mathematics
|
| Genre/Form |
Conference papers and proceedings
|
|
Software.
|
| Form |
Electronic book
|
| Author |
Cooper, S. B. (S. Barry)
|
|
Dawar, Anuj.
|
|
Löwe, Benedikt
|
| ISBN |
9783642308703 |
|
3642308708 |
|
3642308694 |
|
9783642308697 |
|
