Contents -- Preface -- 1. Computation, Information, and the Arrow of Time P. Adriaans & P. van Emde Boas -- 1.1. Introduction -- 1.2. A Formal Framework: Meta-computational Space -- 1.3. Time Symmetries in Meta-computational Space -- 1.4. The Interplay of Computation and Information -- 1.5. Discussion -- 1.6. Conclusion -- References -- 2. The Isomorphism Conjecture for NP M. Agrawal -- Contents -- 2.1. Introduction -- 2.2. Definitions -- 2.3. Formulation and Early Investigations -- 2.4. A Counter Conjecture and Relativizations -- 2.5. The Conjectures for Other Classes -- 2.6. The Conjectures for Other Reducibilities -- 2.6.1. Restricting the input head movement -- 2.6.2. Reducing space -- 2.6.3. Reducing depth -- 2.6.4. Discussion -- 2.7. A New Conjecture -- 2.8. Future Directions -- References -- 3. The Ershov Hierarchy M. M. Arslanov -- Contents -- 3.1. The Hierarchy of Sets -- 3.1.1. The finite levels of the Ershov hierarchy -- 3.1.2. The properties of productiveness and creativeness on the n-c.e. sets -- 3.1.3. The class of the !-c.e. sets -- 3.1.4. A description of the 0 2-sets using constructive ordi- nals -- 3.1.5. The infinite levels of the Ershov hierarchy -- 3.1.6. Levels of the Ershov hierarchy containing Turing jumps -- 3.2. The Turing Degrees of the n-c.e. Sets -- 3.2.1. The class of the n-c.e. degrees -- 3.2.2. The degrees of the n-c.e. sets in the n-CEA hierarchy -- 3.2.3. The relative arrangement of the n-c.e. degrees -- 3.2.4. The cupping, capping and density properties -- 3.2.5. Splitting properties -- 3.2.6. Isolated d-c.e. degrees -- 3.2.7. A generalization -- 3.2.8. Further results and open questions -- References -- 4. Complexity and Approximation in Reoptimization G. Ausiello, V. Bonifaci, & B. Escoffer -- Contents -- 4.1. Introduction -- 4.2. Basic Definitions and Results.

4.3. Reoptimization of NP-hard Optimization Problem -- 4.3.1. General properties -- 4.3.1.1. Hereditary problems -- 4.3.1.2. Unweighted problems -- 4.3.1.3. Hardness of reoptimization -- 4.3.2. Results on some particular problems -- 4.3.2.1. Min Steiner Tree -- 4.3.2.2. Scheduling -- 4.3.2.3. Max Knapsack -- 4.4. Reoptimization of Vehicle Routing Problems -- 4.4.1. The Minimum Traveling Salesman Problem -- 4.4.1.1. The general case -- 4.4.1.2. Minimum Metric TSP -- 4.4.1.3. Minimum Asymmetric TSP -- 4.4.2. The Maximum Traveling Salesman Problem -- 4.4.2.1. Maximum TSP -- 4.4.2.2. Maximum Metric TSP -- 4.4.3. The Minimum Latency Problem -- 4.5. Concluding Remarks -- References -- 5. Definability in the Real Universe S. B. Cooper -- Contents -- 5.1. Introduction -- 5.2. Computability versus Descriptions -- 5.3. Turing's Model and Incomputability -- 5.4. The Real Universe as Discipline Problem -- 5.5. A Dissenting Voice . . . -- 5.6. The Quantum Challenge -- 5.7. Schrödinger's Lost States, and the Many-Worlds Interpretation -- 5.8. Back in the One World . . . -- 5.9. The Challenge from Emergence -- 5.10. A Test for Emergence -- 5.11. Definability the Key Concept -- 5.12. The Challenge of Modelling Mentality -- 5.13. Connectionist Models to the Rescue? -- 5.14. Definability in What Structure? -- 5.15. The Turing Landscape, Causality and Emergence . . . -- 5.16. An Informational Universe, and Hartley Rogers' Programme -- References -- 6. HF-Computability Y. L. Ershov, V. G. Puzarenko, & A. I. Stukachev -- Contents -- 6.1. Introduction -- 6.2. HF-Logic -- 6.3. -Subsets on Hereditarily Finite Superstructures -- 6.4. Reducibilities on Hereditarily Finite Superstructures -- 6.5. Descriptive Properties on Hereditarily Finite Superstructures -- 6.6. -Definability of Structures -- 6.6.1. -Definability on structures: general properties.

6.6.2. -Definability on special structures -- 6.6.3. Special cases of -definability -- 6.7. Semilattices of Degrees of Presentability of Structures -- 6.8. Closely Related Approaches to Generalized Computability -- 6.8.1. BSS-computability -- 6.8.2. Search computability -- 6.8.3. Montague computability -- 6.9. KPU. Examples of Admissible Structures -- 6.9.1. Elements of KPU -- 6.9.2. -subsets -- 6.9.3. Gandy's Theorem -- Acknowledgements -- References -- 7. The Mathematics of Computing between Logic and Physics G. Longo & T. Paul -- Contents -- 7.1. Introduction -- 7.2. Computability and Continuity -- 7.3. Mathematical Computability and the Reality of Physics -- 7.4. From the Principle of Least Action to the Quantum Theory of Fields -- 7.5. Chaotic Determinism and Predictability -- 7.6. Return to Computability in Mathematics -- 7.7. Non-determinism? -- 7.8. The Case of Quantum Mechanics -- 7.9. Randomness, Between Unpredictability and Chaos -- 7.10. General Conclusions -- Acknowledgements -- References -- 8. Liquid State Machines: Motivation, Theory, and Applications W. Maass -- Contents -- 8.1. Introduction -- 8.2. Why Turing Machines are Not Useful for Many Important Computational Tasks -- 8.3. Formal Definition and Theory of Liquid State Machines -- 8.4. Applications -- 8.5. Discussion -- Acknowledgements -- References -- 9. Experiments on an Internal Approach to Typed Algorithms in Analysis D. Normann -- Contents -- 9.1. Introduction -- 9.1.1. Classical computability theory -- 9.1.2. Generalizing computability theory -- 9.1.3. Generalizing finiteness -- 9.1.4. Computability at higher types -- 9.2. Computational Analysis -- 9.2.1. Type two enumerability -- 9.2.2. Domain representability -- 9.2.3. Quotients of countably based spaces -- 9.2.4. A purely internal approach? -- 9.3. Some Typed Hierarchies of Limit Spaces.

9.3.1. Total versus partial functionals -- 9.3.2. The problem with density -- 9.3.3. Probabilistic projections -- 9.4. Domain Representations and Density -- Acknowledgements -- References -- 10. Recursive Functions: An Archeological Look P. Odifreddi -- Contents -- 10.1. Types of Recursion -- 10.1.1. Iteration -- 10.1.2. Primitive recursion -- 10.1.3. Primitive recursion with parameters -- 10.1.4. Course-of-value recursion -- 10.2. The First Recursion Theorem -- 10.2.1. Differentiable functions -- 10.2.2. Contractions -- 10.2.3. Continuous functions -- 10.3. The Second Recursion Theorem -- 10.3.1. The diagonal method -- 10.3.2. The diagonal -- 10.3.3. The switching function -- 10.3.4. Selfreference -- References -- 11. Reverse Mathematics and Well-ordering Principles M. Rathjen & A. Weiermann -- Contents -- 11.1. Introduction -- 11.2. The Ordering 'X0 -- 11.4. Main Theorem -- 11.4.1. Deduction chains in !-logic -- 11.4.2. The infinitary calculus 1 1-CRQ 1 -- 11.5. Ramified Analysis RA1 -- 11.5.1. Finishing the proof of the main theorem -- 11.6. Finishing the Proof of Theorem 11.1.3 -- 11.7. Prospectus -- References -- 12. Discrete Transfinite Computation Models P. D. Welch -- Contents -- 12.1. Introduction -- 12.1.1. The contents -- 12.1.2. Argument -- 12.2. Computation on Integers -- 12.2.1. Transcending the finite through stacking Turing ma- chines -- 12.2.1.1. General relativistic models: Malament-Hogarth Spacetimes -- 12.2.1.2. Etesi & Németi's rotating black hole model -- 12.2.1.3. Hogarth's arithmetically deciding spacetime regions -- 12.2.1.4. A universal constant upper bound for any computation -- 12.2.2. Allowing supertasks -- 12.2.2.1. Punch-hole machines -- 12.2.2.2. Infinite Time Register Machines (ITRMs) -- 12.2.2.3. Infinite Time Turing Machines (ITTMs) -- 12.3. Computation on Reals -- 12.3.1. ITTM computations on reals.

12.4. Computation on Ordinals, and Ordinal Length Machines -- 12.4.1. Ordinal length tapes -- 12.4.1.1. -length tapes -- 12.4.2. Ordinal Register Machines -- 12.5. Theoretical Machine Strength -- Acknowledgements -- References.