## Computability in Context: Computation and Logic in the Real WorldComputability has played a crucial role in mathematics and computer science, leading to the discovery, understanding and classification of decidable/undecidable problems, paving the way for the modern computer era, and affecting deeply our view of the world. Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions about the so-called Turing barrier.This volume addresses various aspects of the ways computability and theoretical computer science enable scientists and philosophers to deal with mathematical and real-world issues, covering problems related to logic, mathematics, physical processes, real computation and learning theory. At the same time it will focus on different ways in which computability emerges from the real world, and how this affects our way of thinking about everyday computational issues. The list of contributors includes: S Abramsky, P Adriaans, M Agrawal, M Arslanov, G Ausiello, J Diaz, Y Ershov, G Longo, W Maass, I Nemeti, A Nerode, D Normann, G Odifreddi, M Rathjen, G Rozenberg, M Vardi, and P Welch. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

3 The Ershov Hierarchy M M Arslanov | 49 |

4 Complexity and Approximation in Reoptimization G Ausiello V Bonifaci B Escoffer | 101 |

5 Definability in the Real Universe S B Cooper | 131 |

6 HFComputability Y L Ershov V G Puzarenko A I Stukachev | 169 |

7 The Mathematics of Computing between Logic and Physics G Longo T Paul | 243 |

Motivation Theory and Applications W Maass | 275 |

9 Experiments on an Internal Approach to Typed Algorithms in Analysis D Normann | 297 |

An Archeological Look P Odifreddi | 329 |

11 Reverse Mathematics and Wellordering Principles M Rathjen A Weiermann | 351 |

12 Discrete Transfinite Computation Models P D Welch | 371 |

### Other editions - View all

Computability in Context: Computation and Logic in the Real World S Barry Cooper,Andrea Sorbi Limited preview - 2011 |

### Common terms and phrases

admissible set Algebra and Logic algorithm approximation arithmetic Arslanov bits c.e. degree c.e. sets circuit classical complete sets computability theory computably enumerable conjecture consider construction constructivizable contains Corollary countable countable structure deﬁne defined Deﬁnition denote deterministic domain dynamical elementarily equivalent equations equivalent Ershov hierarchy example exists formula function f graph halting hereditarily finite superstructures HF(M infinite input instance integers isomorphism iteration ITTM Kleene Lemma linear Math mathematical natural numbers node non-deterministic notion NP-complete NP-hard one-way functions ordinal output pair partial computable function physical polynomial predicate primitive recursion problem proof properties Proposition quantum random readout real numbers Recursion Theory reducibilities register machines relation reoptimization result semilattices sequence signature size-increasing space spacetime string subset tape Theorem tion Traveling Salesman Problem Turing degrees Turing machine universal variables vertex