Computability In Context: Computation and Logic in the Real World

Contents......Page 8
Preface......Page 6
1. Computation, Information, and the Arrow of Time P. Adriaans & P. van Emde Boas......Page 10
1.1. Introduction......Page 11
1.2. A Formal Framework: Meta-computational Space......Page 13
1.3. Time Symmetries in Meta-computational Space......Page 16
1.4. The Interplay of Computation and Information......Page 20
1.5. Discussion......Page 24
1.6. Conclusion......Page 25
References......Page 26
2.1. Introduction......Page 28
2.2. Definitions......Page 29
2.3. Formulation and Early Investigations......Page 32
2.4. A Counter Conjecture and Relativizations......Page 35
2.5. The Conjectures for Other Classes......Page 37
2.6. The Conjectures for Other Reducibilities......Page 39
2.6.1. Restricting the input head movement......Page 40
2.6.2. Reducing space......Page 42
2.6.3. Reducing depth......Page 43
2.6.4. Discussion......Page 48
2.7. A New Conjecture......Page 50
2.8. Future Directions......Page 54
References......Page 55
Contents......Page 58
3.1. The Hierarchy of Sets......Page 59
3.1.1. The finite levels of the Ershov hierarchy......Page 60
3.1.2. The properties of productiveness and creativeness on the n-c.e. sets......Page 63
3.1.3. The class of the !-c.e. sets......Page 66
3.1.4. A description of the  0 2-sets using constructive ordi- nals......Page 71
3.1.5. The infinite levels of the Ershov hierarchy......Page 77
3.1.6. Levels of the Ershov hierarchy containing Turing jumps......Page 81
3.2.1. The class of the n-c.e. degrees......Page 85
3.2.2. The degrees of the n-c.e. sets in the n-CEA hierarchy......Page 88
3.2.3. The relative arrangement of the n-c.e. degrees......Page 91
3.2.4. The cupping, capping and density properties......Page 92
3.2.5. Splitting properties......Page 95
3.2.6. Isolated d-c.e. degrees......Page 96
3.2.7. A generalization......Page 97
3.2.8. Further results and open questions......Page 101
References......Page 106
4. Complexity and Approximation in Reoptimization G. Ausiello, V. Bonifaci, & B. Escoffer......Page 110
4.1. Introduction......Page 111
4.2. Basic Definitions and Results......Page 113
4.3. Reoptimization of NP-hard Optimization Problem......Page 115
4.3.1.1. Hereditary problems......Page 116
4.3.1.2. Unweighted problems......Page 120
4.3.1.3. Hardness of reoptimization......Page 121
4.3.2. Results on some particular problems......Page 123
4.3.2.1. Min Steiner Tree......Page 124
4.3.2.2. Scheduling......Page 125
4.3.2.3. Max Knapsack......Page 126
4.4. Reoptimization of Vehicle Routing Problems......Page 127
4.4.1.1. The general case......Page 129
4.4.1.2. Minimum Metric TSP......Page 130
4.4.1.3. Minimum Asymmetric TSP......Page 131
4.4.2.1. Maximum TSP......Page 133
4.4.3. The Minimum Latency Problem......Page 134
4.5. Concluding Remarks......Page 135
References......Page 136
Contents......Page 140
5.1. Introduction......Page 141
5.3. Turing’s Model and Incomputability......Page 142
5.4. The Real Universe as Discipline Problem......Page 143
5.5. A Dissenting Voice . . .......Page 144
5.6. The Quantum Challenge......Page 146
5.7. Schr¨odinger’s Lost States, and the Many-Worlds Interpretation......Page 148
5.8. Back in the One World . . .......Page 149
5.9. The Challenge from Emergence......Page 151
5.10. A Test for Emergence......Page 155
5.11. Definability the Key Concept......Page 157
5.12. The Challenge of Modelling Mentality......Page 159
5.13. Connectionist Models to the Rescue?......Page 162
5.14. Definability in What Structure?......Page 165
5.15. The Turing Landscape, Causality and Emergence . . .......Page 166
5.16. An Informational Universe, and Hartley Rogers’ Programme......Page 168
References......Page 171
Contents......Page 178
6.1. Introduction......Page 179
6.2. HF-Logic......Page 180
6.3.  -Subsets on Hereditarily Finite Superstructures......Page 192
6.4. Reducibilities on Hereditarily Finite Superstructures......Page 200
6.5. Descriptive Properties on Hereditarily Finite Superstructures......Page 203
6.6.  -Definability of Structures......Page 207
6.6.1.  -Definability on structures: general properties......Page 209
6.6.2.  -Definability on special structures......Page 212
6.6.3. Special cases of  -definability......Page 220
6.7. Semilattices of Degrees of Presentability of Structures......Page 225
6.8.1. BSS-computability......Page 229
6.8.2. Search computability......Page 232
6.8.3. Montague computability......Page 235
6.9.1. Elements of KPU......Page 237
6.9.2.  -subsets......Page 239
6.9.3. Gandy’s Theorem......Page 241
References......Page 243
Contents......Page 252
7.1. Introduction......Page 253
7.2. Computability and Continuity......Page 254
7.3. Mathematical Computability and the Reality of Physics......Page 258
7.4. From the Principle of Least Action to the Quantum Theory of Fields......Page 260
7.5. Chaotic Determinism and Predictability......Page 261
7.6. Return to Computability in Mathematics......Page 267
7.7. Non-determinism?......Page 269
7.8. The Case of Quantum Mechanics......Page 273
7.9. Randomness, Between Unpredictability and Chaos......Page 276
7.10. General Conclusions......Page 277
References......Page 280
8.1. Introduction......Page 284
8.2. Why Turing Machines are Not Useful for Many Important Computational Tasks......Page 292
8.3. Formal Definition and Theory of Liquid State Machines......Page 294
8.4. Applications......Page 299
8.5. Discussion......Page 300
References......Page 302
Contents......Page 306
9.1. Introduction......Page 307
9.1.2. Generalizing computability theory......Page 308
9.1.3. Generalizing finiteness......Page 309
9.1.4. Computability at higher types......Page 311
9.2. Computational Analysis......Page 312
9.2.2. Domain representability......Page 313
9.2.4. A purely internal approach?......Page 315
9.3.1. Total versus partial functionals......Page 317
9.3.2. The problem with density......Page 318
9.3.3. Probabilistic projections......Page 319
9.4. Domain Representations and Density......Page 328
References......Page 335
Contents......Page 338
10.1.1. Iteration......Page 339
10.1.2. Primitive recursion......Page 341
10.1.3. Primitive recursion with parameters......Page 342
10.1.4. Course-of-value recursion......Page 343
10.2. The First Recursion Theorem......Page 345
10.2.1. Differentiable functions......Page 347
10.2.2. Contractions......Page 348
10.2.3. Continuous functions......Page 349
10.3. The Second Recursion Theorem......Page 351
10.3.1. The diagonal method......Page 352
10.3.3. The switching function......Page 353
10.3.4. Selfreference......Page 355
References......Page 357
11. Reverse Mathematics and Well-ordering Principles M. Rathjen & A. Weiermann......Page 360
11.1. Introduction......Page 361
11.2. The Ordering \'X0......Page 364
11.4.1. Deduction chains in !-logic......Page 366
11.4.2. The infinitary calculus  1 1-CRQ 1......Page 369
11.5. Ramified Analysis RA1......Page 374
11.5.1. Finishing the proof of the main theorem......Page 376
11.7. Prospectus......Page 377
References......Page 378
Contents......Page 380
12.1.1. The contents......Page 381
12.1.2. Argument......Page 382
12.2. Computation on Integers......Page 383
12.2.1.1. General relativistic models: Malament–Hogarth Spacetimes......Page 385
12.2.1.2. Etesi & N´emeti’s rotating black hole model......Page 387
12.2.1.3. Hogarth’s arithmetically deciding spacetime regions......Page 388
12.2.1.4. A universal constant upper bound for any computation......Page 391
12.2.2.1. Punch-hole machines......Page 393
12.2.2.2. Infinite Time Register Machines (ITRMs)......Page 394
12.2.2.3. Infinite Time Turing Machines (ITTMs)......Page 395
12.3. Computation on Reals......Page 401
12.3.1. ITTM computations on reals......Page 404
12.4. Computation on Ordinals, and Ordinal Length Machines......Page 407
12.4.1. Ordinal length tapes......Page 408
12.4.1.1.  -length tapes......Page 410
12.4.2. Ordinal Register Machines......Page 411
12.5. Theoretical Machine Strength......Page 412
References......Page 416