Includes index.

SpringerLink Springer Engineering eBooks 2017 English+International

Preface; Contents; 1 Nonuniversality in Computation: Fifteen Misconceptions Rectified; 1.1 Introduction; 1.1.1 The Main Theorem; 1.1.2 A Simple Example: Time-Varying Variables; 1.1.3 Consequences; 1.1.4 Motivation; 1.2 Preliminaries; 1.3 Inherently Parallel Computations; 1.3.1 Time-Varying Variables; 1.3.2 Time-Varying Computational Complexity; 1.3.3 Rank-Varying Computational Complexity; 1.3.4 Interacting Variables; 1.3.5 Uncertain Time Constraints; 1.3.6 Computations Obeying Mathematical Constraints; 1.3.7 The Universal Computer Is a Myth; 1.4 Misconceptions and Replies

1.4.1 Misconception 11.4.2 Misconception 2; 1.4.3 Misconception 3; 1.4.4 Misconception 4; 1.4.5 Misconception 5; 1.4.6 Misconception 6; 1.4.7 Misconception 7; 1.4.8 Misconception 8; 1.4.9 Misconception 9; 1.4.10 Misconception 10; 1.4.11 Misconception 11; 1.4.12 Misconception 12; 1.4.13 Misconception 13; 1.4.14 Misconception 14; 1.4.15 Misconception 15; 1.5 Conclusion; References; 2 What Is Computable? What Is Feasibly Computable? A Physicist's Viewpoint; 2.1 What Is Computable? What Is Feasibly Computable? Different Aspects of These Questions

2.2 Non-Standard Physical Processes Can Help Computations: Examples Based On Specific Physical Models2.3 What if No Final Theory Is Possible?; 2.3.1 No Physical Theory Is Perfect: How to Formalize the Widely Spread Physicists' Belief; 2.3.2 The Use of Physical Computations Can Enhance Computations; 2.3.3 The Use of Physical Observations Can Help in Solving NP-Complete Problems; 2.4 What if We Take into Account that We Are only Interested in Processing Physical Data; 2.5 Conclusions; References; 3 The Ideal Energy of Classical Lattice Dynamics; 3.1 Introduction; 3.1.1 Ideal Energy

3.1.2 Local Change3.1.3 Two Examples; 3.2 Scalable Soft Sphere CA; 3.2.1 Ideal Energy and Momentum; 3.2.2 Rescaling the Collision; 3.3 Elastic String CA; 3.3.1 Discrete Wave Model; 3.3.2 Exact Wave Behavior; 3.3.3 Overall Transverse Motion; 3.3.4 Ideal Energy and Momentum; 3.3.5 Rest Frame Energy; 3.4 Discussion; References; 4 An Analogue-Digital Model of Computation: Turing Machines with Physical Oracles; 4.1 Introduction; 4.2 Physical Oracles; 4.2.1 Types of Physical Oracles; 4.2.2 The Smooth Scatter Experiment; 4.3 The Smooth Scatter Machine

4.3.1 Communicating with the Smooth Scatter Experiment4.3.2 Measurement Algorithms; 4.4 Computational Power of the Smooth Scatter Machine; 4.4.1 Nonuniform Complexity Classes; 4.4.2 The Cantor Set mathcalC3; 4.4.3 Lower Bound for the Infinite Precision; 4.4.4 Smooth Scatter Machine as a Biased Coin; 4.4.5 Lower Bound for the Unbounded and Fixed Precisions; 4.4.6 Boundary Numbers; 4.4.7 Upper Bound for the Infinite Precision; 4.4.8 Probabilistic Query Trees; 4.4.9 Upper Bound for the Unbounded Precision; 4.4.10 Upper Bound for the Fixed Precision; 4.5 Upper Bound with Explicit Time Technique