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

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
A 5 n  −  o ( n ) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function....Pages 432-439
Local Induction and Provably Total Computable Functions: A Case Study....Pages 440-449
What is Turing’s Comparison between Mechanism and Writing Worth?....Pages 450-461
Substitutions and Strongly Deterministic Tilesets....Pages 462-471
The Computing Spacetime....Pages 472-484
Unifiability and Admissibility in Finite Algebras....Pages 485-495
Natural Signs....Pages 496-506
Characteristics of Minimal Effective Programming Systems....Pages 507-516
After Turing: Mathematical Modelling in the Biomedical and Social Sciences....Pages 517-527
Existence of Faster than Light Signals Implies Hypercomputation already in Special Relativity....Pages 528-538
Turing Computable Embeddings and Coding Families of Sets....Pages 539-548
On the Behavior of Tile Assembly System at High Temperatures....Pages 549-559
Abstract Partial Cylindrical Algebraic Decomposition I: The Lifting Phase....Pages 560-570
Multi-valued Functions in Computability Theory....Pages 571-580
Relative Randomness for Martin-Löf Random Sets....Pages 581-588
On the Tarski-Lindenbaum Algebra of the Class of all Strongly Constructivizable Prime Models....Pages 589-598
Lower Bound on Weights of Large Degree Threshold Functions....Pages 599-608
What Are Computers (If They’re not Thinking Things)?....Pages 609-615
Compactness and the Effectivity of Uniformization....Pages 616-625
On the Computability Power of Membrane Systems with Controlled Mobility....Pages 626-635
On Shift Spaces with Algebraic Structure....Pages 636-645
Finite State Verifiers with Constant Randomness....Pages 646-654
Game Arguments in Computability Theory and Algorithmic Information Theory....Pages 655-666
Turing Patterns in Deserts....Pages 667-674
Subsymbolic Computation Theory for the Human Intuitive Processor....Pages 675-685
A Correspondence Principle for Exact Constructive Dimension....Pages 686-695
Low n Boolean Subalgebras....Pages 696-702
Bringing Up Turing’s ‘Child-Machine’....Pages 703-713
Is Turing’s Thesis the Consequence of a More General Physical Principle?....Pages 714-722
Some Natural Zero One Laws for Ordinals Below ε 0 ....Pages 723-732
On the Road to Thinking Machines: Insights and Ideas....Pages 733-744
Making Solomonoff Induction Effective....Pages 745-754
Back Matter....Pages -