How the World Computes

Name: How the World Computes | Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012, Proceedings

Barry S. Cooper Anuj Dawar Benedikt Löwe(Herausgeber*in)

Springer (Verlag)

Erschienen am 28. Mai 2012

XVIII, 756 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-30870-3 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Reviewers
Table of Contents
Ordinal Analysis and the Infinite Ramsey Theorem
Introduction
The Semi-formal System ACA
An Upper Bound for ACA0+iRT
A Lower Bound for ACA0+ iRT
Conclusion
References
Curiouser and Curiouser: The Link between Incompressibility and Complexity
Introduction
Cast of Characters
Some Odd Inclusions
An Upper Bound on Complexity
Towards a Characterization of BPP
Speculations
References
Information and Logical Discrimination
Background and Motivation
Conceptions of Logical Consequence
Informational Content and Logical Space
Dynamics of Information
Information and Discrimination
Two Principles and the Crucial Inversion
Logic and Granularity
Issues and Open Problems
Information and the Dynamic Turn in Logic
Guises of Logical Discrimination
Informational Semantics and the Philosophy of Information
References
Robustness of Logical Depth
Introduction
Preliminaries
Kolmogorov Complexity
Instability of Logical Depth
Conclusions
References
Turing's Normal Numbers: Towards Randomness
On the Problem of Giving Instances of Normal Numbers
Turing's Construction of Normal Numbers
Turings's Theorem 1: A Construction via Finite Approximations
Turing's Theorem 2: An Algorithm to Output Normal Numbers
Towards the Theory of Algorithmic Randomness
References
Logic of Ruler and Compass Constructions
Introduction
Is Euclid's Reasoning Constructive?
The Elementary Constructions
Models of Ruler-and-Compass Geometry
Three Versions of the Parallel Postulate
Constructive Geometry and Euclidean Fields
What ECG Proves to Exist, Can Be Constructed with Ruler and Compass
Independence Results for the Parallel Axioms
Conclusions
References
On the Computational Content of the Brouwer Fixed Point Theorem
Introduction
The Weihrauch Lattice
Closed Sets and Trees of Rational Complexes
Brouwer's Fixed Point Theorem and Connected Choice
AspectsofDimension
Conclusions
References
Square Roots and Powers in Constructive Banach Algebra Theory
Introduction
Products of Hermitian/Positive Elements
The Path to Theorem 2
References
The Mate-in-n Problem of Infinite Chess Is Decidable
References
A Note on Ramsey Theorems and Turing Jumps
Introduction
RT3, ACA0, and ?-Exponentiation
?nRTn, ACA 0, and Iterated ?-Exponentiation
LargeSets,ACA+0 , and the e Function
References
Automatic Functions, Linear Time and Learning
Introduction
Automatic Functions and Linear Time
Linear Time Learners
Conclusion
References
An Undecidable Nested Recurrence Relation
Introduction
TagSystems
A Modified Tag System
Simulating a Tag System with a Reverse Tag System
Simulating a Reverse Tag System with a Recurrence
Reducing A to B
Concluding Remarks
References
Hard Instances of Algorithms and Proof Systems
Introduction
Preliminaries
Hard Sequences for Algorithms
Hard Sequences for Proof Systems
Hard Subsets
Assuming the Measure Hypothesis
Getting Hard Sequences in an Effective Way
References
On Mathias Generic Sets
Introduction
Definitions
Basic Results
The Forcing Relation
Degrees of Mathias Generics
References
Complexity of Deep Inference via Atomic Flows
Introduction
Deep Inference
AtomicFlows
Truth Tables and Tableaux
Separations via the Functional Pigeonhole Principle
Polynomial-Size Proofs of the Functional Pigeonhole Principle
A Polynomial Simulation of Resolution and Some Extensions
A Simulation of Dag-Like Cut-Free Gentzen
Conclusions
Atomic Flows as a Tool for Complexity Analysis
Dag-Like Cut-Free Gentzen Systems and Variations
Stronger Systems
References
Connecting Partial Words and Regular Languages
Introduction
Definability by Substitutions
Languages of Partial Words
References
Randomness, Computation and Mathematics
Introduction
Basics
Randomness and Classical Computability
(Some) Applications
Left Out
Ergodic Theory
Differentiability Is the Same as Randomness
Relationships between Random Strings and Complexity Classes
Physics
Conclusion
References
Learning, Social Intelligence and the Turing Test Why an "Out-of-the-Box" Turing Machine Will Not Pass the Turing Test
Introduction
Learning vs. Computation
Human Intelligence
Design and the Turing Test
Intelligence in General
Understanding Ourselves
Conclusions
References
Confluence in Data Reduction: Bridging GraphTransformation and Kernelization
Introduction
Basic Concepts of Kernelization and Critical Pair Analysis
Case Study Clique Cover
Case Study Partial Clique Cover
Discussion and Future Work
References
Highness and Local Noncappability
Introduction
Requirements
A QCeStrategy
An RCeStrategy
An SCe,i Strategy
An He Strategy
Interaction between Strategies
References
Turing Progressions and Their Well-Orders
Turing Progressions and Modal Logic
OmegaSequences
Basic Properties of Omega Sequences
Successor Coordinates
Equal Coordinates
Limit Coordinates
References
A Short Note on Spector's Proof of Consistency of Analysis
References
Sets of Signals, Information Flow, and Folktales
A Theory of Information Flow
Information Flow via Sets of Signals
Learning and Intensionality
Folktales and Narrative Structure
Information in Individual Narratives
References
On the Foundations and Philosophy of Info-metrics
Background, Objective and Motivation
Examples and Framework
Universality
The Starting Premise - The Observer
Open Questions
Summary
References
On Mathematicians Who Liked Logic
Cleft
Newman's Course at Cambridge
Newman's Way in to Logic
After Vienna
References
Densities and Entropies in Cellular Automata
Introduction
Preliminaries
Configurations
Symbolic Dynamics
Cellular Automata and Determinism
Effectiveness
Results
Construction
Density Encoding
Checking Homogeneity
Checking the Density
From Density to Entropy
The Second Dimension
Conclusion
References
Foundational Analyses of Computation
Introduction
Turing
Discussion
Kolmogorov
Gandy
Comments
Analyzing Computations on Their Native Levels of Abstraction
Motivation
Constraints
Definition and the Representation Theorem
Deriving Church's Thesis
References
Turing Machine-Inspired Computer Science Results
References
NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
Introduction
NP-Completeness
Fixed-Parameter Tractability
General Terms and Observations
High Potential Sequences
Low Potential Sequences
Conclusion and Open Questions
References
A Direct Proof of Wiener's Theorem
Introduction
A Direct Proof of Wiener's Theorem
Constructing the Inverse
A More General Result
References
Effective Strong Nullness and Effectively Closed Sets
Introduction
Background
Notation
Effective Strong Nullness
Combinatorial Theorem
Effective Strong Nullness and Diminutiveness
Lattice Operators
Closure Properties
MLR and DNC
Kolmogorov Complexity, and K-Triviality
References
Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable
Introduction
Background
Slim and Fat Tree Languages
Slim Tree Automatic Structures Are Word Automatic
Monadic Second Order Logic
The Encoding and Preservation of Regularity
Preservation of Automaticity
Fat Tree Automatic Ordinals Are Not Word Automatic
Conclusions
References
On the Relative Succinctness of Two Extensions by Definitions of Multimodal Logic
Introduction
Preliminaries
Multimodal Logic
Extended Syntax Trees
Succinctness
MainResults
Conclusion and Open Questions
References
On Immortal Configurations in Turing Machines
The Immortality Problem
Definitions
Effective Sets
Effective Subshifts
Proof of the Main Result
Counter Machines
Turing Machines
The Main Construction
Conclusion
References
A Slime Mold Solver for Linear Programming Problems
Introduction
The Generalized Physarum Solver
Proof of Convergence
LP with Positive Costs
LP with General Costs
Relations to Other LP Solvers
The Discrete Physarum Solver
Finite Difference Approximation
The Assignment Problem
References
Multi-scale Modeling of Gene Regulation of Morphogenesis
Introduction
Methods
Results and Discussion
References
Tree-Automatic Well-Founded Trees
Introduction
Preliminaries
Bounding the 8-rank of Tree-Automatic Well-Founded Trees
The Isomorphism Problem for Well-Founded Tree-Automatic Trees
References
Infinite Games and Transfinite Recursion of Multiple Inductive Definitions
Introduction
Preliminaries
Weak Determinacy of Games and Inductive Definitions
Inductive Definitions
Difference Sets
Tranfinite Recursion of Inductive Definitions
Multiple Inductive Definitions and Determinacy of Games
Conclusion and Future Studies
References
A Hierarchy of Immunity and Density for Sets of Reals
Introduction
Summary
Notation and Convention
Computability with Layers
Density and Immunity
Learnability on Topological Spaces
Degrees of Difficulty
Layer Density as a Degree-Theoretic Invariant
Topological Games and Popperian Learnability
References
How Much Randomness Is Needed for Statistics?
Introduction
Hippocratic Martingales
Hippocratic Stochasticity and KL Randomness
Computable Randomness
Kolmogorov-Loveland Stochasticity and Randomness
Definitions
Hippocratic Stochasticity Is Not Stochasticity
Kolmogorov-Loveland Randomness
References
Towards a Theory of Infinite Time Blum-Shub-Smale Machines
Introduction
Clockable Ordinals
Connections to Other Models of Computation
Remarks and Open Questions
References
Turing Pattern Formation without Diffusion
Introduction
Finding Turing Patterns in Real Systems
Turing Patterns in Vertebrate Skin
Zebrafish
Identification of the Network at the Cellular and Molecular Level
Short Range Repulsion of the Pigment Cells Is Correspond to the Local Positive Feedback [2]
Long Range Survival Help by the Locally Competing Cell Is Correspond to the Long Negative Feedback (Unpublished Data)
No Diffusion in the Identified Network
Does the Discovered Mechanism Belong to "Turing Mechanism"?
Future Directions
References
Degrees of Total Algorithms versus Degrees of Honest Functions
Introduction
Preliminaries
Cai's Degree Structure
The Honest Elementary Degrees
The Honest 0-Elementary Degrees
Honest Associates and PA+ Degrees
The Isomorphism Theorem
References
A 5n - o(n) Lower Bound on the Circuit Size over U2 of a Linear Boolean Function
Introduction
Definitions
Known Lower Bounds
Single-Output Functions
Multi-output Functions
A5n - o(n) Lower Bound
References
Local Induction and Provably Total Computable Functions: A Case Study
Introduction
Local Induction and Restricted Iteration
MainResult
References
What is Turing's Comparison between Mechanism and Writing Worth?
Introduction
Mechanism as a Scientific Paradigm
The Long History of Writing
Writing Numbers and Languages
Three Technical Innovations in the History of Verbal Writing
The Alphabetic Combinators
The Undecidable
References
Substitutions and Strongly Deterministic Tilesets
Definitions
A Strongly Deterministic Aperiodic Tileset
NE-Soficity of Substitutions Limit Sets
4-Way Soficity of Substitutions Limit Sets
References
The Computing Spacetime
Introduction
The Problem of Quantum Gravity
Quantum Graphity
Qubits of Adjacency
Interacting Matter and Geometry
Calculating the Speed of Light as Propagation of Information
Analogue Black Holes
Geometry: What the Matter Sees
Discussion
References
Unifiability and Admissibility in Finite Algebras
Introduction
Preliminaries
Unifiability
Admissibility
Concluding Remarks
References
Natural Signs
Introduction
Correlational Signs
A Reference Class for Determining Natural Correlational Signs
Answering the Fundamental Question
Generalizing to Non-correlational Signs
Natural Signs Based on a Single Repetition
Natural Signs of Individuals
Ovelapping Natural-Sign Patterns
References
Characteristics of Minimal Effective Programming Systems
Introduction
Preliminaries
Results
References
After Turing: Mathematical Modelling in the Biomedical and Social Sciences
Introduction
How the Leopard Gets Its Spots
Brain Tumours: Enhancing Imaging Techniques, Quantifying Therapy Efficacy and Estimating Patient Life Expectancy
Virtual Gliomas for Anatomically Correct Brains: Enhanced Imaging and Current Limitations
Approximate in vivo Patient Survival Time
Marital Interaction and Divorce Prediction
References
Existence of Faster than Light Signals Implies Hypercomputation already in Special Relativity
Introduction
Hypercomputation in SR
The Language of Our Axiom Systems
Axioms of Special Relativity
Hypercomputation in AccRel
Concluding Remarks
References
Turing Computable Embeddings and Coding Families of Sets
Introduction
Facts about Theory of Real Closed Fields
Results
Construction of Embeddings
References
On the Behavior of Tile Assembly System at High Temperatures
Introduction
Abstract Tile Assembly Model
Behavioral Equivalences among TASs
Threshold Programming
FINDOPTIMALSTRENGTH is NP-hard
Tile Complexity at High Temperatures
References
Abstract Partial Cylindrical Algebraic Decomposition I: The Lifting Phase
Introduction
CAD Preliminaries
CAD Construction and Evaluation for ? RCF
Partial CAD
Abstract Partial CAD
Stages, Theatres and Lifting
Experimental Results
Conclusion
References
Multi-valued Functions in Computability Theory
Introduction
Background
The Category of Multi-valued Functions
The Lattice of Many-One Degrees
Some Examples
Computable Many-One Reductions
Polynomial-Time Many Reductions
Outlook
References
Relative Randomness for Martin-L¨of Random Sets
Introduction
Preliminaries
Semi G-Randomness
Conclusions and Future Research
References
On the Tarski-Lindenbaum Algebra of the Class of all Strongly Constructivizable Prime Models
Preliminaries
Main Claim
A Technical Statement
Proof to Part (c) of Theorem 1
FinalRemarks
References
Lower Bound on Weights of Large Degree Threshold Functions
Introduction
Construction of the Function
2O(2n/4) Lower Bound
Proof of Theorem 3
Improved Lower Bound
References
What Are Computers (If They're not Thinking Things)?
Our Technologies
Replacing-Technologies
Intentional Actions and Non-intentional Operations
The Intentional Stance?
Conclusion
References
Compactness and the Effectivity of Uniformization
Introduction
Type-2-Theory, Enumerability and Computational Compactness
Conformal Mappings for Simply and Multiply Connected Domains
Uniformization
Discussion
References
On the Computability Power of Membrane Systems with Controlled Mobility
Introduction
Enhanced Mobile Membranes with Controlled Mobility
Computability Power of Controlled Mobility
Conclusion
References
On Shift Spaces with Algebraic Structure
Introduction
Definitions
Cellwise Lattice Subshifts
General Algebraic Subshifts
F-Linear Cellular Automata
Future Work
References
Finite State Verifiers with Constant Randomness
Introduction
Preliminaries
2pfa Verifiers with Constant Randomness and 2nfa(k)'s
Open Questions
References
Game Arguments in Computability Theory and Algorithmic Information Theory
Friedberg's Unique Numbering
Total Conditional Complexity
Epstein-Levin Theorem
Muchnik-Vyugin Theorem
References
Turing Patterns in Deserts
Introduction
ModelEquations
Travelling Wave Solutions
Conclusion
References
Subsymbolic Computation Theory for the Human Intuitive Processor
Effective Procedures vs. Intuitive Cognitive Processes
Subsymbolic Automata
From Symbolic to Vectorial Representations
Linearly Computable Functions by Recursion
Grammars and Optimization
Quantization
Optimization and Universal Grammar
References
A Correspondence Principle for Exact Constructive Dimension
Notation and Preliminaries
Gauge Functions and Hausdorff's Original Approach
Previous Results
Exact Hausdorff Dimension and Martingales
Effectivisation of Exact Hausdorff Dimension
TheResults
Constructive Dimension
Computable Dimension
References
Lown Boolean Subalgebras
Introduction
TheHistory
The Main Result
References
Bringing Up Turing's 'Child-Machine'
A 'Guiding Principle'
Intelligent Behavior versus Completely Disciplined Behavior
Teachers, Singular and Plural
Imitation and Intelligence
References
Is Turing's Thesis the Consequenceof a More General Physical Principle?
Introduction
PhysicalModels
Computable Physical Models
Continuous Models
References
Some Natural Zero One Laws for Ordinals Below e0
Introduction
Some Basic Results
Refinements
References
On the Road to Thinking Machines: Insights and Ideas
Introduction
The Principles
Escaping the Turing Test
Escaping Biologism
Internal World Models
Mirror Neurons
Algebra of Thoughts
Habits
Understanding of Understanding
Thinking
Global Workspace Theory
(Dis)solving the Hard Problem of Consciousness
Episodic Memory
Real Time Massive Data Processing
De-embodiment of Robotic Humanoid Cognitive Systems
Conclusion
References
Making Solomonoff Induction Effective Or: You Can Learn What You Can Bound
Introduction
The Generator Space
Algorithmic Ontology: Programs as Generators
Learning Systems
S-Driven Learning Systems
Generator-Predictor Theorem
Learnability and Reverse Mathematics
Synchronous Learning Frameworks
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken