Computability

Throughout this book we use the language of naive set theory as our metalanguage. In most parts no particular knowledge from mathematics or computer science is assumed. Special concepts from mathematics are introduced shortly when they are needed.

Flowcharts are a common tool for describing everyday algorithms. Most computer programming languages admit flowchart programming. Also several definitions of computability use models based on the concept of flowchart. In this chapter general definitions of flowcharts and machines (machine := flowchart + input encoding + output encoding) and their semantics are given. Two very useful basic transformations for flowcharts, simulation and refinement, which we shall use repeatedly in later proofs, will be introduced and proved to be correct. Finally the change of input and output encoding is considered. The aim of this chapter is to give a framework for formulating several later proofs more rigorously and transparently and in addition to supply a precise method for developing programs together with correctness proofs. Roughly speaking, a flowchart is a list of operations and tests (called statements) on a dataset D, where the order of execution is determined by a finite table. Before defining a certain class of flowcharts formally we explain the idea by an example.

In this chapter we introduce register machines and study the functions computed by them, the register computable functions. As we shall discuss later, the register computable functions very likely represent those functions on the natural numbers which are “absolutely” computable in the intuitive sense.

In Chapter 1.2 we have defined the computable functions on ℕ using register machines. This definition enables good understanding of the concept of computability. In this chapter we define the computable functions in a quite different way. We first define the primitive recursive functions and then the μ-recursive functions and finally prove that the μ-recursive functions coincide with the (register) computable functions. The primitive recursive functions form a class of total computable functions which contains all (total) functions of practical interest. However this class is too large to be of real importance outside of mathematical logic and theoretical computer science.

The computable functions on numbers can also be defined by WHILE-programs. Here the idea of computing on registers is combined with the idea of inductive definition. While-programs allow constructing very transparent algorithms and support correctness proofs.

In 1937, A.M. Turing proposed a machine model for defining computability. We shall use Turing’s model for defining the computable word functions f:(W(Σ))k → W(Σ), where Σ is an alphabet. The physical model of a Turing machine is a tape on which a read/write head operates controlled by a finite device (or a flowchart) like a computer operates on a potentially infinite magnetic tape.

Since tape machines or one tape Turing machines are not very appropriate for practical programming of word functions, in this chapter we introduce a generalization of the register machines from numbers to words, the stack machines. Stack machines, especially the generalized stack machines, are a very useful and natural tool for formulating algorithms which operate on words. We shall prove that the stack machine computable word functions are exactly the (tape) computable word functions.

In Chapter 1.2 we introduced the computable functions on numbers using register machines, and in Chapter 1.5 we defined the computable word functions by means of Turing machines. Since numbers are not words and words are not numbers the two classes are incomparable. We shall prove, however, that by means of a standard numbering v_Σℕ → W(Σ) the computable number functions can be transformed into the computable word functions (over Σ) and vice versa. This shows that the two definitions of computability are not totally independent. Church’s thesis which states that the computable number functions are exactly the intuitively computable number functions will be discussed. Finally, we prove that there are functions which are not computable.

In the previous chapters we have studied computable functions f: ℕk → N and f: (W(Σ))k→W(Σ). The concept of computability is now used to define recursiveness and recursive enumerability of subsets A ⊆ ℕk and B ⊆ (W(Σ))k.

In the previous chapters we have studied different kinds of machines, the computable functions and recursive and r.e. sets. The theorems we have proved are generally of a constructive nature themselves. We have shown e.g.: “for any f ∈ P(2), $$ \tilde \mu \left( f \right) \in {P^{\left( 1 \right)}}^{\prime \prime } $$” (Theorem 1.2.12), “for any stack machine there is a Turing machine computing the same function” (Theorem 1.6.7), “for any r.e. A ⊆ ℕ there is some recursive B ⊆ ℕ2 such that A is the projection of B” (Theorem 1.8.4). The proofs of these and many other theorems, however, yield more information. We have for example shown: “there is an effective procedure which for any register machine M produces a register machine M′ such that $$ {f_{M'}} = \tilde \mu {\left( {{f_M}} \right)^{\prime \prime }}, $$, or “there is an effective procedure which for any register machine M produces a register machine M′ such that f_m, is a total function and dom(f_M) is the projection of f_M′-1{0}”. In order to formulate these observations precisely one can introduce standard names for register machines (or the corresponding computable functions) which are appropriate words. Then the effective procedures can be represented by computable functions on the names. Since computability on words can be reduced to computability on numbers (Theorem 1.7.5), we shall use numbers as names which yields a formally simpler theory.

In Chapter 1.9 we have proved that the halting problem and the self applicability problem for φ are (recursively) unsolvable (Theorem 1.9.16(2)). In Part 2 of this book several other problems which can be derived from φ will be shown to be unsolvable, and we shall study “degrees of unsolvability”. The discussion at the end of Chapter 1.9 indicates that there are fundamental applications of recursion theory in logic. A special chapter in Part 2 will be devoted to some of these questions. In this chapter some decision problems from other parts of mathematics will be considered. A decision problem is defined by a set M and a subset $$ {M_o} \subseteq M. $$. The problem is to decide for any m ∈ M whether m belongs to M_o or not. In the case of the halting problem M = ℕ and M_o = K_φo. If M is not a set of the numbers or of the words over some alphabet then it is not clear what “decide” means. In this case more information has to be supplied to specify the decision problem. Usually a notation ν of M, i.e. a surjective function ν : W(∑)→M, is given. Also a numbering ν : ℕ→M could be used. W.l.g. we consider the case of a notation here. By Theorem 1.8.9 both approaches yield the same decidability results.

The fundamental notion of computability theory is that of the computable functions f : ℕk→ ℕ, where ℕ ={0,1,2,...} is the set of natural numbers and the dotted arrow indicates a partial function. By definition, a function f : ℕk→ℕ (k∈ℕ) is computable iff there is a register machine which computes it (c f. Chapter 1.2, Def. 3). The domain of f consists of those inputs for which the register machine halts. There are several other equivalent definitions (see Part 1 of this book). By Church’s Thesis the computable functions are exactly those number functions which are intuitively computable. This thesis is not a theorem since the concept “intuitively computable” is not precisely defined. The theory of computability does not depend on the validity of Church’s Thesis which is only used for interpreting the results. By P(k)we denote the set of k-ary partial recursive functions f : ℕk→ℕ, by R(k) we denote the set of k-ary total recursive functions (c f. Def. 1.7.6). For proving that a function f : ℕk→ℕ is computable, usually it is shown that a register machine exists which computes f. In practice such a proof is not elaborated in all details. The first essential step consists of the definition of an abstract machine M ( = input encoding + output encoding + flowchart, c f. Chapter 1.1) and a proof of f = f_M (correctness). The flowchart of the machine should be sufficiently detailed such that transformation of the machine M into a register machine by refinement and simulation is a routine exercise which generally is not executed. Usually it suffices to specify the flowchart only informally and incompletely using e.g. ALGOL like notation such that a precise specification can be derived easily. In future we shall proceed in this manner.

In Part 1 of this book we have defined the computable functions f : ℕk→ℕ and the computable functions f : (W(∑))k→ W(∑). These definitions, however, are not applicable to functions on the rational numbers, on finite graphs, on the real numbers, etc. It is not even defined whether a “standard numbering” ν : ℕ→W(∑) is computable or not. Obviously, new definitions are needed. One method for defining the computable functions f : M₁→ M₂ is to develop a new computability model for the sets M₁ and M₂. As we have seen in Part 1, any new computability model requires the development of an extended theory and the justification of a thesis like Church’s Thesis. We already know that a computability theory may be reducible to another one, e.g. computability on words may be reduced to computability on numbers by a standard numbering v : ℕ→ W(∑) (Theorem 1.7.5), or computability of functions ℕk→ ℕ can be reduced to computability of functions ℕ→ℕ by the tupling function π(k) (Lemma 1.2.16). This indicates a second method for introducing computability of functions M₁→ M₂. The elements of M₁ and M₂ are named (or encoded) by numbers, and a function f: M₁→ M₂ is called computable iff it results from a computable function which transforms names (i.e. numbers) into names. In this case no new theory of computability has to be developed, but still theses corresponding to Church’s Thesis have to be discussed, namely whether the “namings” of M₁ and M₂ are “intuitively effective”. Of course, this method is only applicable to denumerable sets since the set of available names, namely ℕ, is only denumerable. A naming by natural numbers will be called a numbering. In this chapter we shall study effectivity w.r.t. given numberings. The question of effectivity of numberings will be discussed later in a separate chapter.

In this chapter we continue the study of the recursive and the recursively enumerable subsets of ℕ. First more examples for recursively enumerable sets which are not recursive are given. The non-recursiveness is proved by reduction to the self applicability problem or in one case by a new kind of diagonalization. Several characterizations of the recursive and the recursively enumerable sets are introduced and the corresponding numberings are compared w.r.t. reducibility. In most cases the nonexistence of a computable function can be reduced to the unsolvability of the halting problem. Finally the φ-recursive and the φ-recursively enumerable subsets of P(1) are studied. Rice’s theorem states that no non-trivial property P(1) is φ-recursive. A more general lemma gives two necessary conditions for φ-r.e. sets, by which many subsets of P(1) can be proved to be not φ-r.e.

In Chapter 1.9 we have introduced the reducibility relation ≤ for numberings, and in Chapter 2.2 we have proved that two numberings of a set M define the same computability theory for M iff they are equivalent. We shall now introduce a stronger reducibility, the one-one reducibility, together with the induced one-one equivalence and isomorphism of numberings. We shall prove Myhill’s theorem which states that (for total numberings) isomorphism and one-one equivalence coincide. We introduce cylinders and study the relation between reducibility and one-one reducibility. We conclude with some further useful properties.

In this chapter we present a simple theorem, the recursion theorem or the fixed-point theorem of recursion theory, which provides a means for answering a number of seemingly difficult problems for precomplete numberings among which are the numberings, φ, W, and cf_K, the characteristic function of the self applicability problem.

As we already know the set K= {i | i ∈ dom(φ_i)} is recursively enumerable and not recursive. In the set RE of recursively enumerable subsets of N the set K has several characteristic remarkable properties: it is creative, it is m-complete, it is 1-complete, and its complement is the smallest productive set. As we shall see, creativity and productivity have interesting applications in logic. As a kind of generalization of creativity we finally introduce effective inseparability and prove a further generalization of Rice’s theorem for precomplete numberings.

In Chapter 2.2 we have defined how a numbering v of a set S induces a computability theory on the set S. We have shown that the numbering v of a set S is determined uniquely (up to equivalence) by the computability theory induced by it (Lemma 2.2.8, Conclusion 2.2.9). In this chapter we shall study for which effectivity conditions numberings satisfying these conditions exist. As a main result we shall show that for sets which are defined as closures numberings defined via generation trees are natural.

In chapter 2.6 we have indicated how appropriate finite path trees can be used for specifying infinite computable production processes. We shall generalize Definition 2.7.5 of trees by also admitting nodes with infinite branching. Such nodes will serve as names for functions with infinitely many arguments such as “$$ \mathop {\lim }\limits_{n \to \infty } $$”. For measuring the height of such trees the denumerable ordinal numbers, i.e. the numbers of Cantor’s second number class, are needed. We shall define the effective numberings of the computable trees over the (unrestricted) signature a. As the main application we derive a standard numbering of the computable ordinals. We prove that the computable ordinals can be characterized by total numberings of well-orders for which v(i) ≤ v(j) is decidable. Our approach differs slightly from Kleene’s original one.

In mathematics statements about mathematical objects are formulated and proved. In logics the formulation of statements (the syntax), the meaning of statements (the semantics), truth, proofs,etc. are studied. In this chapter we shall exhibit some applications of recursion theory to logics. Decidability, productivity, and effective inseparability will play an important role.

For comparing the difficulty of sets of numbers, in Chapter 2.3 we have introduced (many-one) reducibility: A ≤ B iff (∀x) (x ∈ A ⇔ f(x) ∈ B) for some total recur- sive function f ∈ R(1). If A ≤ B then by Lemma 2,3.4, B recursive ⇒ A recursive and B r.e. ⇒ A r.e. Let A ≤ B. Thus, for deciding x ∈ A it is sufficient to answer the question “f(x) ∈ B? ”. The following examples show that there are more general possibilities to reduce questions “x ∈ A ?” computably to questions “y ∈ B?”

This chapter will be concerned with a very general kind of reducibility called Turing reducibility, and a classification of the arithmetical sets by the Kleene hierarchy or arithmetical hierarchy. Finally truth-table reducibility which is weaker than many-one reducibility but stronger than Turing reducibility is introduced. As a main tool we shall apply the relativized recursion theory introduced in Chapter 2.10. We prove some very basic facts and a deeper theorem by Friedberg and Muchnik which says that there are two recursively enumerable sets which are incomparable w.r.t. Turing reducibility. Among the possibly nonrecursive sets the arithmetical sets are of particular interest. They can be classified w.r.t. the degree of noncomputability by the Kleene hierarchy. Truth-table reducibility is defined as a special case of Turing reducibility. An extensive study and comparison of all the reducibilities is beyond the scope of this book.

The theory of computational complexity is concerned with measuring the difficulty of computations. Let P be a program of a programming language (e.g. PASCAL or “tape machines”). For any input x there is a computation c(P,x)= (α_o,α₁,…) which is a sequence of configurations. If this sequence is infinite, the value f_P(x), the result of applying program P to input x, does not exist, and the computational complexity R_p(x) of the computation c(P,x) is undefined. If c(P,x)= (α_o,…,α_n) is finite, then the result f_p(x) can be extracted from the last configuration α_n and the computational complexity is an appropriate function of the sequence (α_o,…,α_n) There are many possibilities for defining R_p(x). Examples: the length n of the computationmax{lg v_l(α_i) ∣ 0≤ i ≤ n}Σ{1g v₁(α_i) ∣ 0≤ i≤ n}v₂−1 c(P,x)(where v₁ is an “effective” notation of the configurations and v₂ is an “effective” numbering of computations). A reasonable computational complexity measure should at least satisfy the following conditions: (∀x)dom(f_p) = dom(R_p) for all programs P{(P,x,t) ∣ R_p(x) = t} is decidable.

In Type 1 recursion theory we have defined computability explicitly on numbers and on words and we have shown that both approaches are essentially equivalent (see Theorem 1.7.5). Computability on other denumerable sets can be reduced to computability on ℕ via numberings or notations. In this chapter we shall introduce three explicit definitions of Type 2 computability and prove that they are essentially equivalent. Any “natural” kind of computability on some other Type 2 set should be reducible to any one of these three definitions by means of a representation.

In this chapter we lay the basis for a unified Type 2 recursion theory. Our investigations from Chapter 3.1 and especially Theorem 3.1.14 show that it suffices to study continuity and computability on Baire’s space B . We shall choose the set B = ℕℕ as our standard set on which we develop a theory of continuity (w.r.t. Baire’s topology) and of computability. The theory turns out to be formally similar to Type 1 recursion theory. Most definitions and theorems will appear in a topological and in a computational version in accordance with our previously explained program for Type 2 theory. First we introduce a representation $$ \hat \varphi $$ : B →[B → B_o] of the continuous functions from B to B_o which is effective: it satisfies the Type 2 utm-theorem and smn-theorem. From $$ \hat \varphi $$ we derive a representation φ : B →[B → B] where [B →B] is the set of continuous functions г: B → B the domains of which are the G_δ-subsets of B , and we derive a representation x: B→[B→ℕ] of the set of the continuous functions г: B → ℕ the domains of which are the open subsets of B . The representations φ and x satisfy the utm-theorem and the smn-theorem. As a counterpart of the recursively enumerable subsets in Type 1 theory we study the open and the computably open subsets of B. This Type 2 theory of open subsets of B is formally very similar to the Type 1 theory of the recursively enumerable sets.

In Chapter 3.1 we have introduced Type 2 constructivity and computability on the spaces P_ω, B_o, and ℂ_o explicitly and we have shown that each of these concepts can be derived from any other one. In Chapter 3.2 we have chosen Baire’s space B as our basic Type 2 space. We have developed a theory of constructivity and a more special theory of computability both of which are formally very similar to ordinary Type 1 recursion theory. In this chapter the basic Type 2 theory on Baire’s space will be extended to a theory of representations.

It cannot be expected that arbitrary representations have interesting constructive or computational properties. In this chapter we introduce some types of “effective” representations. For any topological space with T_o-topology and countable base a distinguished equivalence class of effective representations (the admissible representations) can be introduced by natural topological requirements. These requirements correspond to the axiomatic characterization of the numbering φ of the partial recursive functions by the smn-theorem and the utm-theorem (see Chapter 2.1). Final topologies which play an important role in this theory are studied in advance. Admissible representations have several natural properties; especially for admissible representations of T_o-spaces topological continuity coincides with continuity w.r.t. the representations. For any given numbering of a base of a T_o-space, we define the computationally admissible representations. For separable metric spaces the Cauchy-representations are introduced which turn out to be admissible. The concept of admissible representations is sufficiently powerful in order to define constructivity and computability in a natural way in functional analysis and measure theory.

In Chapter 3.1 we have defined constructivity and computability on the sets P_ω, IB_o, and ℂ_o explicitly (Def. 3.1.3, 3.1.8, 3.1.10). The three definitions are very similar. They are special cases of a general theory, the theory of complete partial orders (cpo’s). Complete partial orders are used as domains for the semantics (the denotational semantics) of programming languages. But independently of this application they are an interesting general model for studying Type 2 constructivity and computability. We shall not develop a general theory of cpo’s but essentially study a special class of cpo’s, the class of boundedly-complete algebraic cpo’s with countable basis. This chapter contains the topological framework. CPO’s and the continuous functions are defined. Algebraic cpo’s are introduced. For any algebraic cpo a topology can be defined such that order-continuity and topological continuity coincide. It is shown that the class of cpo’s is closed w.r.t. sum and product. The most remarkable property is that the space of the continuous functions between two cpo’s is a cpo again. The algebraic basises of the standard sum, product, and function space of b-complete algebraic cpo’s are defined explicitly. Finally the recursion theorem for cpo’s is proved. Constructivity and computability are investigated in the next two chapters.

For any representation δ there is a derived numbering v_δ, defined by ν_δ(i):=δφ_i, of the δ-computable elements. In this chapter the relation between δ-computability and ν_δ-computability is investigated. It is easy to show that the restriction of a (δ,δ,)-computable function to the computable elements is (ν_δ,ν_δ’)-computable. The converse does not seem to be true in general. Only for two special cases a positive answer is known: for “effective” metric spaces (special cases have been proved independently by Ceitin, by Kreisel, Lacombe, and Shoenfield, and by Moschovakis) and for “computable” cpo’s (a special case has been proved by Myhill and Sheperdson). As a corollary we obtain a theorem which characterizes the ν_δ-r.e. subsets of the δ-computable elements for “computable” cpo’s (Rice /Shapiro theorem). The proofs of the main theorems are rather sophisticated.

As we have already noted, cpo’s are used for defining the semantics of programming languages. In the theory of semantics, cpo’s which satisfy certain recursion equations are needed. Different formalisms for solving such recursion equations have been developed. In this chapter we shall use the cpo theory itself for studying an appropriate class of cpo’s. We shall construct a “super cpo”, the elements of which are cpo’s and solve fixed point equations by applying the fixed point operator to appropriate computable functions on the super cpo.

Type 2 theory of continuity and computability has interesting applications in Analysis. In this chapter some basic questions on constructivity in Analysis are studied by means of the tools which have been developed in the preceding chapters.