Ebook: How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings

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.

---

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.

---

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.
Content:
Front Matter....Pages -
Ordinal Analysis and the Infinite Ramsey Theorem....Pages 1-10
Curiouser and Curiouser: The Link between Incompressibility and Complexity....Pages 11-16
Information and Logical Discrimination....Pages 17-28
Robustness of Logical Depth....Pages 29-34
Turing’s Normal Numbers: Towards Randomness....Pages 35-45
Logic of Ruler and Compass Constructions....Pages 46-55
On the Computational Content of the Brouwer Fixed Point Theorem....Pages 56-67
Square Roots and Powers in Constructive Banach Algebra Theory....Pages 68-77
The Mate-in-n Problem of Infinite Chess Is Decidable....Pages 78-88
A Note on Ramsey Theorems and Turing Jumps....Pages 89-95
Automatic Functions, Linear Time and Learning....Pages 96-106
An Undecidable Nested Recurrence Relation....Pages 107-117
Hard Instances of Algorithms and Proof Systems....Pages 118-128
On Mathias Generic Sets....Pages 129-138
Complexity of Deep Inference via Atomic Flows....Pages 139-150
Connecting Partial Words and Regular Languages....Pages 151-161
Randomness, Computation and Mathematics....Pages 162-181
Learning, Social Intelligence and the Turing Test....Pages 182-192
Confluence in Data Reduction: Bridging Graph Transformation and Kernelization....Pages 193-202
Highness and Local Noncappability....Pages 203-211
Turing Progressions and Their Well-Orders....Pages 212-221
A Short Note on Spector’s Proof of Consistency of Analysis....Pages 222-227
Sets of Signals, Information Flow, and Folktales....Pages 228-236
On the Foundations and Philosophy of Info-metrics....Pages 237-244
On Mathematicians Who Liked Logic....Pages 245-252
Densities and Entropies in Cellular Automata....Pages 253-263
Foundational Analyses of Computation....Pages 264-275
Turing Machine-Inspired Computer Science Results....Pages 276-282
NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs....Pages 283-292
A Direct Proof of Wiener’s Theorem....Pages 293-302
Effective Strong Nullness and Effectively Closed Sets....Pages 303-312
Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable....Pages 313-322
On the Relative Succinctness of Two Extensions by Definitions of Multimodal Logic....Pages 323-333
On Immortal Configurations in Turing Machines....Pages 334-343
A Slime Mold Solver for Linear Programming Problems....Pages 344-354
Multi-scale Modeling of Gene Regulation of Morphogenesis....Pages 355-362
Tree-Automatic Well-Founded Trees....Pages 363-373
Infinite Games and Transfinite Recursion of Multiple Inductive Definitions....Pages 374-383
A Hierarchy of Immunity and Density for Sets of Reals....Pages 384-394
How Much Randomness Is Needed for Statistics?....Pages 395-404
Towards a Theory of Infinite Time Blum-Shub-Smale Machines....Pages 405-415
Turing Pattern Formation without Diffusion....Pages 416-421
Degrees of Total Algorithms versus Degrees of Honest Functions....Pages 422-431
Local Induction and Provably Total Computable Functions: A Case Study....Pages 432-439
What is Turing’s Comparison between Mechanism and Writing Worth?....Pages 440-449
Substitutions and Strongly Deterministic Tilesets....Pages 450-461
The Computing Spacetime....Pages 462-471
Unifiability and Admissibility in Finite Algebras....Pages 472-484
Natural Signs....Pages 485-495
Characteristics of Minimal Effective Programming Systems....Pages 496-506
After Turing: Mathematical Modelling in the Biomedical and Social Sciences....Pages 507-516
Existence of Faster than Light Signals Implies Hypercomputation already in Special Relativity....Pages 517-527
Turing Computable Embeddings and Coding Families of Sets....Pages 528-538
On the Behavior of Tile Assembly System at High Temperatures....Pages 539-548
Abstract Partial Cylindrical Algebraic Decomposition I: The Lifting Phase....Pages 549-559
Multi-valued Functions in Computability Theory....Pages 560-570
Relative Randomness for Martin-L?f Random Sets....Pages 571-580
On the Tarski-Lindenbaum Algebra of the Class of all Strongly Constructivizable Prime Models....Pages 581-588
Lower Bound on Weights of Large Degree Threshold Functions....Pages 589-598
What Are Computers (If They’re not Thinking Things)?....Pages 599-608
Compactness and the Effectivity of Uniformization....Pages 609-615
On the Computability Power of Membrane Systems with Controlled Mobility....Pages 616-625
On Shift Spaces with Algebraic Structure....Pages 626-635
Finite State Verifiers with Constant Randomness....Pages 636-645
Game Arguments in Computability Theory and Algorithmic Information Theory....Pages 646-654
Turing Patterns in Deserts....Pages 655-666
Subsymbolic Computation Theory for the Human Intuitive Processor....Pages 667-674
A Correspondence Principle for Exact Constructive Dimension....Pages 675-685
Bringing Up Turing’s ‘Child-Machine’....Pages 686-695
Is Turing’s Thesis the Consequence of a More General Physical Principle?....Pages 696-702
On the Road to Thinking Machines: Insights and Ideas....Pages 703-713
Making Solomonoff Induction Effective....Pages 714-722
Back Matter....Pages 723-732
....Pages 733-744