Computability in Context

The following sections are included:

• Preface

• Contents

In this chapter we investigate the relation between information and computation under time symmetry. We show that there is a class of nondeterministic automata, the quasi-reversible automata (QRTM), that is the class of classical deterministic Turing machines operating in negative time, and that computes all the languages in NP. The class QRTM is isomorphic to the class of standard deterministic Turing machines TM, in the sense that for every M ∈ TM there is a M⁻¹ in QRTM such that each computation on M is mirrored by a computation on M⁻¹ with the arrow of time reversed. This suggests that non-deterministic computing might be more aptly described as deterministic computing in negative time. If M_i is deterministic then is non deterministic. If M is information discarding then M⁻¹ “creates” information. The two fundamental complexities involved in a deterministic computation are Program Complexity and Program Counter Complexity. Programs can be classified in terms of their “information signature” with pure counting programs and pure information discarding programs as two ends of the spectrum. The chapter provides a formal basis for a further analysis of such diverse domains as learning, creative processes, growth, and the study of the interaction between computational processes and thermodynamics.

In this chapter, we survey the arguments and known results for and against the Isomorphism Conjecture.

In this chapter we investigate set-theoretic properties and the Turing degree structure of the hierarchy of -sets, which is well known in the literature as the Ershov hierarchy.

In this chapter the following model is considered: We assume that an instance I of a computationally hard optimization problem has been solved and that we know the optimum solution of such an instance. Then a new instance I' is proposed, obtained by means of a slight perturbation of instance I. How can we exploit the knowledge we have on the solution of instance I to compute an (approximate) solution of instance I' in an efficient way? This computation model is called reoptimization and is of practical interest in various circumstances. In this chapter we first discuss what kind of performance we can expect for specific classes of problems and then we present some classical optimization problems (i.e. Max Knapsack, Min Steiner Tree, Scheduling) in which this approach has been fruitfully applied. Subsequently, we address vehicle routing problems and we show how the reoptimization approach can be used to obtain good approximate solutions in an efficient way for some of these problems.

Logic has its origins in basic questions about the nature of the real world and how we describe it. This chapter seeks to bring out the physical and epistemological relevance of some of the more recent technical work in logic and computability theory.

We survey the results on HF-computability (computability on hereditarily finite superstructures), an approach to abstract computability based on the notion of Σ-definability in admissible sets.

Do physical processes compute? And what is a computation? These questions have gained a revival of interest in recent years due to new technologies in physics, new ideas in computer sciences (for example quantum computing, networks, non-deterministic algorithms), and new concepts in logic. In this chapter we examine a few directions, as well as the problems they bring to the surface.

The Liquid State Machine (LSM) has emerged as a computational model that is more adequate than the Turing machine for describing computations in biological networks of neurons. Characteristic features of this new model are (i) that it is a model for adaptive computational systems, (ii) that it provides a method for employing randomly connected circuits, or even “found” physical objects for meaningful computations, (iii) that it provides a theoretical context where heterogeneous, rather than stereo typical, local gates, or processors increase the computational power of a circuit, (iv) that it provides a method for multiplexing different computations (on a common input) within the same circuit. This chapter reviews the motivation for this model, its theoretical background, and current work on implementations of this model in innovative artificial computing devices.

The chapter consists of four sections. First we discuss aspects of generalized computability theory with a focus of how various approaches to abstract computability theory relate to computational analysis. Emphasis is put on the distinction between internal and external algorithms. Then we prove some old and some new results related to the typed hierarchy of hereditarily total objects over complete and separable normed vectorspaces, with the aim of carrying out the arguments within the framework of Kuratowski limit spaces.

In the final section we prove a topological consequence of an assumption that the total continuous functions from one complete, separable metric space to another is dense in the sense of domain theory. It turns out that this assumption will have consequences for how the connectedness properties of the two metric spaces relate.

The following sections are included:

• Types of Recursion
  • Iteration
  • Primitive recursion
  • Primitive recursion with parameters
  • Course-of-value recursion

• The First Recursion Theorem
  • Differentiable functions
  • Contractions
  • Continuous functions

• The Second Recursion Theorem
  • The diagonal method
  • The diagonal
  • The switching function
  • Selfreference

• References

This chapter is concerned with generally sentences of the form “if X is well ordered then f(X) is well ordered”, where f is a standard proof theoretic function from ordinals to ordinals. It has turned out that a statement of this form is often equivalent to the existence of countable coded ω-models for a particular theory T_f whose consistency can be proved by means of a cut elimination theorem in infinitary logic which crucially involves the function f. To illustrate this theme, we shall focus on the well-known φ-function which figures prominently in so-called predicative proof theory. However, the approach taken here lends itself to generalization in that the techniques we employ can be applied to many other proof-theoretic functions associated with cut elimination theorems. In this paper we show that the statement “if X is well ordered then φX0 is well ordered” is equivalent to ATR₀. This was first proved by Friedman (see [7]) using recursion-theoretic and combinatorial methods. The proof given here is proof-theoretic, the main techniques being Schütte's method of proof search (deduction chains) [15], generalized to ω logic, and cut elimination for infinitary ramified analysis.

Discrete computing models, such as that of the Turing machine or of Register machines, can be allowed to run transfinitely if suitable limit ordinal behavior is described. This chapter relates such models to classical accounts of higher type recursion theory, going back to Kleene. Using such models as a yardstick, one can analyse more modern models, such as computation in particular physical spacetimes, to give bounds on the complexity of such forms of computation. Computation on ordinals and set recursion are briefly discussed.