This chapter should be understood as a very brief review of algorithmics and the theory of recursive functions. For an elementary introduction, see, for instance, David Harel's book Algorithmics []. Comprehensive treatments of the subject are Hartley Rogers' Theory of Recursive Functions and Effective Computability [] and P. Odifreddi's Classical Recursion Theory []. Other introductions are M. Davis, Computability & Unsolvability [], M. L. Minsky, Computation: Finite and Infinite Machines [] and part C of the Handbook of Mathematical Logic [].

1.1  Algorithm and effective computability

The present concept of formal computation has been developed from the experience of practical ``manual'' calculation, at least up to some limited resource level. How could the intuitive concept of ``manual'' or ``mechanic computation'' be formalised? (In the computer sciences, what is called ``mechanic'' is often referred to as ``deterministic.'' In the physical context, such a terminology may give rise to confusion with the term ``deterministic system,'' which will be characterised by some ``mechanically'' computable evolution function but not necessarily ``mechanically'' computable parameter values.) Take, for instance, an intuitive, pragmatic understanding of ``mechanic computation,'' put forward by Alan M. Turing [] in the 30's: ``whatever can (in principle) be calculated on a sheet of paper by the usual rules is computable.'' The question whether or not this - or any other (possibly more sophisticated) - understanding of ``mechanic'' computation is adequate, has (at least) two aspects: (i) syntax, investigated by formal logic, mathematics and the computer sciences and (ii) physics.

One important result of syntactic arguments is the concept of ``universal computation,'' as envisioned by K. Gödel, J. Herbrand, St. C. Kleene, A. Church and, most influentially, by A. M. Turing. Universal computation is usually developed by introducing a very precise (elementary) model of computation, e.g., the Turing machine, a Cellular Automaton et cetera. It is then shown that, provided it is ``sufficiently complex,'' this model comprises all ``reasonable'' instances of computation. I.e., adding additional components to such a machine does not change its computational capacity qualitatively. (Yet it may change its efficiency in terms of time, storage requirements, program length et cetera.) Furthermore, all such ``universal'' models of computation turn out to be equivalent in the sense that there is a one-to-one translation of one into the other; i.e., every calculation that can be performed by any one of them can be done by all of the others as well. It is often assumed that universal computation remains unaffected by the specific physical realisation of the computing device. I.e., it does not really matter (in principle) what physical base you use for computing - doped silicon, light, nerve cells, billiard balls - as long as your devices work ``mechanically'' and are ``sufficiently complex'' to support universal computation.

Nevertheless, the syntax of universal computation is based on primary intuitive concepts of ``reasonable'' instances of ``mechanic'' computation, which refer to physical insight; i.e., which refer to the types of processes which can be performed in the physical world. In this sense, the level of physical comprehension sets the limits to whatever is acceptable as valid method of computation. If, for instance, we could employ an ``oracle'' (the term ``oracle'' will be specified later), our wider notion of ``mechanic'' computation would include oracle computation. Likewise, a computationally more restricted universe would intrinsically imply a more restricted concept of ``mechanic'' computation. For an early and brilliant discussion of this aspect the reader is referred to A. M. Turing's original work []. As D. Deutsch puts it ([], p. 101),

``The reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics `happen to' permit the existence of physical models for the operations of arithmetic such as addition, subtraction and multiplication. If they did not, these familiar operations would be non-computable functions. We might still know of them and invoke them in mathematical proofs (which would presumably be called `non constructive') but we could not perform them.''

`` ¼ how can we ever exclude the possibility of our presented, some day (perhaps by some extraterrestrial visitors), with a (perhaps extremely complex) device or ``oracle'' that ``computes'' a non computable function?''

Consider, for example, electronic computing, which has transformed our comprehension of computation dramatically, shifting it from ``number-crunching'' to symbolic calculation, visualisation, automation, artificial intelligence and the creation of ``virtual realities.'' Yet, as long as electronic circuits act as ``mechanic'' devices, electronics will not change our concept of universal ``mechanic'' computing. Thus electronic computing is not an example for the type of physical process which would make necessary a revision of concepts of computation.

The question remains whether such revisions will become necessary as our abilities to stimulate and control physical processes advance. It remains to be seen whether new capacities will become feasible by the use of the continuum in classical physics (see below) or by quantum effects [,,,,,,,,] or more remote possibilities. It can for instance be conjectured that quantum computation will not enlarge the scope of computation because the enhanced physical capacities of quantum mechanics will inevitably be washed away by noise; i.e., by the randomness of quantum events and by the amplification of noise when information in the quantum domain gets interpreted classically. This resembles the ``peaceful coexistence'' between quantum theory and relativity (cf. section , p. ).

We do not know whether our own self is limited by the ``mechanic'' computational capacities of the part of the world we presently cope with scientifically. Kurt Gödel (Collected Works II [], p. 305) seemed to have believed that the mind transcends mechanical procedures. See also P. Odifreddi [], p. 113, and the remark by H. Weyl, quoted on page pageref.

Thus, if the term ``mechanic'' is a label referring to rules which completely determine some ``reasonable'' actions of computation, then whatever is considered as ``reasonable'' action of computation has to be specified also by physics.

The following notion of ``algorithm'' or ``effective computation'' is motivated by those types of tasks which can actually be performed in the physical world. Therefore, its features are bounded (from above), excluding computations in the limit of infinite time, storage space, program length et cetera.

[Algorithm, effective computability] 
An algorithm is an abstract recipe of finite size, prescribing a process which might be carried out ``mechanically'' by some computing agent, such as a human or a computer and which terminates after some finite time.

An effective computation, or effective procedure C, is some ``mechanic'' procedure which can be applied to any of a certain class of symbolic inputs s and which will eventually yield, for some inputs, a symbolic output t. The process is written similar to functional notation C(s)=t.

Remarks:

(i) An algorithm needs not to be defined for all input values. This corresponds to a partial function, whose domain is not all of \N (for details, see 1.2, p. pageref). In such a case, the procedure might go on forever, never halting.

(ii) Although the input and output sequences as well as the size of the ``scratch paper'' (internal memory) have to be finite, no restriction is imposed on their actual sizes. The same is true for the length of the description of the algorithm as well as its execution time. This renders the definition hard to operationalise, since, for instance, relatively ``small'' programs may take a ``large'' time to execute and may produce ``huge'' output (for details, see , p. ).

(iii) The above definition of algorithm and effective computability is informal. The question if there exist formal notions corresponding to this heuristic approach is nontrivial. In particular, the term ``mechanic'' has to be specified formally and sufficiently comprehensive. The Church-Turing thesis (see below) gives a positive answer which, due to the principal incompatibility between the informal, intuitive (``algorithm'') and the formal (``recursive function'') approach, remains conjectural. To specify this connection, a brief characterisation of the term ``recursive function'' will be given in the next section.

(iv) Analogue computation is not effective in the above sense, since its feature of continuity does not correspond to any meaningful ``mechanical'' process.

(v) The input can be eliminated by substituting a constant for each input parameter, thereby converting, say, a FORTRAN statement such as READ (*,*) A into A=¼. In that way, input code can be converted to program code, and vice versa. See also type-free coding in chapter 4, p. pageref.

Since the present understanding of ``mechanic'' computation has been developed from the computations which can be actually realised, it is tautological that, indeed, there exist physical systems which are universal computers (at least up to some finite computational resources). The circularity of this argument is evident. A constructive ``proof'' of this conjecture is the assembly of a ``universal'' computer (here the quotes refer to the finiteness of the computer's resources) such as a personal computer workstation (insert your favourite brand here:) ``¼'', Charles Babbage's Analytical Engine [] et cetera. These computers are ``universal'' because it is possible to implement a program which simulates any other (not necessarily universal) computer such as a Turing machine (with finite tape). Their universality is only limited by the finiteness of their resources.

1.2  Recursive functions

The notion of effective computation will now be formalised by defining a specific model of computation which is (hopefully) comprehensive enough to correspond properly to the heuristic concept of algorithm. [Partial function, total function] The notion of partial and total function is defined as follows: A partial function f(x)=z, with x,z Î \N is a singe-valued function, i.e., the functional value z is determined uniquely. The domain of f is domain(f)={ x | "z = f(x)} Ì \N . The term partial expresses the fact that the domain of f may not be all of \N. If domain(f)=\N, f is called a total function. f is defined (convergent) at x if x Î domain(f), expressed by f(x)¯ ; otherwise f is undefined (divergent) at x, expressed by f(x)­ .

1.2.1  Primitive recursive function

(i)

All constant functions, f(x₁,¼,x_k)=m, are in C, 1 £ k,  0 £ m;

(ii)

The successor function, f(x)=x+1, is in C;

(iii)

All identity functions, f(x₁,¼,x_k)=x_i, are in C, 1 £ i £ k;

(iv)

If f is a function of k variables in C, and g₁,¼,g_k are (each) functions of m variables in C, then the function h(x₁,¼,x_m)=f(g₁(x₁,¼,x_m),¼ ,g_k(x₁,¼,x_m)) is in C, 1 £ k,m;

(v)

if h is a function of k+1 variables in C, and g is a function of k-1 variables in C, then the unique function f of k variables satisfying f(0,x₂,¼,x_k)=g(x₂,¼,x_k) , f(y+1,x₂,¼,x_k)=h(y,f(y,x₂,¼,x_k),x₂,¼ ,x_k) is in C, 1 £ k.

It would have been more elegant to use the l-notation for characterising C (for details, see H. Rogers [], p. 6), but as this notation is difficult to interpret for the unfamiliar reader, the standard functional notation was used.

Example:

The following primitive recursive definition yields the Fibonacci sequence
0,1,1,2,3,5,8,¼:

Yet, primitive recursion, as introduced in 1.2.1, does not comprehend the full realm of effective computability. It can be shown that there exist algorithmic functions of the natural numbers which grow faster than any primitive recursive function. This has been, for instance, discussed in depth in Róza Péter's book Rekursive Funktionen [], p. 86, by C. Calude, S. Marcus and I. Tevy [] and by H. Rogers [], p. 8. The first example of a recursive function which is not primitive recursive was obtained independently by W. Ackermann [] and the Romanian of Swiss origin G. Sudan []. It is interesting that these examples are not just mathematical curiosities (they are very useful in compiler testing, for instance), but as has been pointed out by C. Calude [], most recursive functions (see definition 1.2, p. pageref) are not primitive recursive, just as most reals are not recursive. A particular example will be given next.

Counterexample:

One strategy for obtaining counterexamples of evidently recursive functions which are not primitive recursive is to try to construct functions which grow ``very fast.'' Consider, for instance, the function f(x)=A(x,x,x), where the Ackermann generalised exponential A is defined by the successive iteration

Another, strategy is diagonalization (see below). Diagonalization is actually a very similar strategy. Consider functions f₁(n) < f₂(n) < f₃(n) < ¼ and g(n)=f_n(n)+1. g grows faster than all f's. For, if g(n) would correspond to some f_i(n), then for n=i the contradiction f_n(n)=g(n)=f_n(n)+1 (wrong) would follow.

In summary, the notion of primitive recursive functions turns out to be too weak to correspond to the algorithmic notion of effective computability.

1.2.2  Diagonalization

Assume now that h were primitive recursive. If this would be the case, h would turn up in the enumeration of the primitive recursive functions somewhere; say at the yth place. Hence,

One possible way to avoid this contradiction (and at the same time maintain functional enumeration) is to assume that the functions g_i are partial functions. Thereby, if in the above construction, g_y(y) needs not be defined, the contradiction ``g_y(y)=g_y(y)+1'' needs not show up.

1.2.3  Partial recursive function

(i)

by the substitution of a numeral expression for a variable symbol throughout an entire equation;

(ii)

by the use of one equation to substitute ``equals for equals'' at every occurrence in a second equation;

(iii)

by the evaluation of an instance of the successor function f(x)=x+1.

An equation is deducible from P if it is obtained in the course of some computation from P. Imagine a standard list of all equations deducible from P. Then given any P and any numerical input, the principle output is defined to be the first numerical output in the standard list generated from the set of instructions P. The resulting relation between input and principal output defines a partial recursive function f_P, which can be associated with the original set of instructions P. In this way one obtains the class of partial recursive functions.

Remarks:

(i) The class of primitive recursive functions can be embedded into the class of recursive functions. The extension of recursive functions over primitive recursive functions consists in the addition of the operation of seeking indefinitely through some standard list for the suitable equation.

(ii) One may suspect that the course of computation is not uniquely determined by the input and by the recursive relations P. Moreover, two different outputs may be obtained from the same input by different computations. These difficulties are circumvented by defining the value of the function to be the first occurrence in an effectively computable standard list.

(iii) The type-free representation of the recursive functions by combinatory logic and, more specifically, by the lambda calculus. In this representation, no difference is made between a ``function'' and its ``argument'' and ``value(s).''

(iv) There ``exist'' non recursive functions which grow too fast to be effectively computable. One example is the busy beaver function S<sub>U</sub>(n) which, roughly speaking, is defined to be the greatest number producible on a computer U by programs of program length less than or equal to n. (For a precise definition, see , p. .) S<sub>U</sub>(n) is a non recursive function; nevertheless it can also be used for upper bounds on the runtime of such programs; see , p. . That this function grows ``very fast'' indeed can be seen from a program evaluating the Ackermann generalised exponential A(n,n,n); with S_U(n) >> A(n,n,n). A computer implementation of A requires programs of ``small'' length, yet, for large n, A(n,n,n) is considerably ``large.'' This applies to computer programs which are permitted to have sufficient size to implement the Ackermann generalised exponential and other ``fast growing'' functions. (On the contrary, a restriction to ``very small size'' program codes of only a view bits length would not allow the implementation of A(n,n,n) or similar, fast growing algorithms.) Indeed, if the busy beaver function would be ``growing slowly,'' one would be able to solve all halting problems of finite-size programs (p. ).

1.2.4  Enumeration of partial recursive functions

The set of primitive recursive functions is one-to-one enumerable. In the same way, it is possible to enumerate all recursive functions, or, equivalently, the sets of instructions P. This statement will not be proved here; informally it may be seen as a direct consequence of an effective enumeration of all sets of instructions P. I.e., every integer x can be associated with a partial recursive function y_x (corresponding to a set of instructions P_x) which is at the (x+1)'st place of this enumeration. [Gödel number of recursive function] 
P_x is the set of instructions associated with the integer x in the fixed enumeration of all sets of instructions. x=# (P_x) is called index or Gödel number of P_x. # is the associated recursive Gödel function.

We shall use the method of Gödel numbers to derive the cardinality of the class of recusive functions. The following statements hold:

(i)

There are exactly À₀ (a countable infinity of) partial recursive functions. The partially recursive functions can be recursively enumerated.

(ii)

There are exactly À₀ total recursive functions. The total recursive functions cannot be recursively enumerated.

Informally stated, the non recursive enumerability of the total recursive functions originates in the impossibility to recursively determine which function is a partial function and which one is a total function. This is a consequence of the recursive unsolvability of the halting problem (cf. section , p. ).

Proof:

Since all constant functions (with values in \N) are recursive and |\N | = À₀, there are at least À₀ constant functions. The Gödel numbering shows that there are at most À₀ partial recursive functions. By a similar argument as in the section dealing with diagonalization (p. pageref), the assumption of the enumeration of all total recursive functions yields a contradiction.

A probably more intuitive, algorithmic, proof is the enumeration of all Turing machines. (For a definition of a Turing machine, see 1.3.1, p. pageref.) Such an explicit enumeration of Turing machines is, for instance, outlined in M. Davis' [], chapter 4.)

Remarks:

(i) Unlike the primitive recursive functions (which are total functions), the class of recursive functions contains partial functions. Therefore, the argument against the enumeration of all algorithmically definable functions using diagonalization (p. pageref) does not apply here. Moreover, as will be seen from the recursive unsolvability of the halting problem (see chapter , p. ), it is in general undecidable if a recursive function converges or diverges at some particular argument.

(ii) The inverse of the Gödel function # may be partial or total. In the above definition, #^-1 is total. For an example of a construction of the Gödel number # (t) corresponding to a term t, see definition 4.3, p. pageref. This definition can be used to enumerate all recursive function with a slight change in notation, i.e., whenever we have to code ``+'' or some other algebraic operation allowed in a recursion we use the code for `` ~ '' or some other symbol which we dont use in this context. In this example, #^-1 is a partial function.

1.2.5  Existence of uncomputable reals

A somewhat related subject are mathematical proof methods which do not have any ``constructive'' or algorithmic flavour, for instance the principle of the excluded middle. One example is a proof of the following theorem: ``There exist irrational numbers x,y Î \R - \Q with x^y Î \Q.'' Proof: case 1: Ö2 ^Ö2 Î \Q ; case 2: Ö2 ^Ö2 Ï \Q, then Ö2 ^{Ö2 Ö2} = 2 Î \Q. The question which one of the two cases is correct; i.e., which number is rational, remains unsolved in the context of the proof.

Informally, recursive reals may be described as the real numbers whose expressions as a decimal are calculable ``bit by bit'' by finite means, i.e., by effective computations (c.f., []). This sloppy definition may give rise to confusions; in particular the term ``bit by bit'' needs an explanation: One might, for instance, conclude correctly that all rationals, all rational powers of rationals (e.g., Ö2), Euler's number e, the number p et cetera are computable. But then, one might be tempted to wrongly infer that the halting probability W (p. ) is computable too, since G. Chaitin has published an algorithm for computing W in the limit of infinite time []. Yet, one necessary condition for a real to be computable is that it converges effectively (i.e., that there exists a computable radius of convergence). - This is what is meant by the phrase ``bit by bit.'' This criterion (effectively computable radius of convergence) is not satisfied by any computation for W. For a detailed definition of recursive reals, see definition 1.6, p. pageref, as well as M. B. Pour-El and J. I. Richards, Computability in Analysis and Physics [], as well as the forthcoming book Computability - A Mathematical Sketchbook by D. S. Bridges [], among others.

The following statements hold:

(i)

There are exactly À₀ (a countable infinity of) recursive reals.

(ii)

The set of recursive reals is not recursively enumerable. I.e., there does not exist an effective enumeration of all (countable many) recursive reals.

(iii)

``Almost all'' reals are non recursive.

Proof:

ad (i) Since all constant functions (with values in \N) are recursive and |\N | = À₀, there are at least À₀ recursive reals. By theorem 1.2.4, there are at most denumerable many (i.e., À₀) partial recursive functions (one may think of an enumeration of all Turing machines).

ad (ii) Proof by diagonalization: assume that there exists an effectively computable enumeration of the decimal reals in the interval [0,1] of the form

In contradistinction, there exists an effectively computable enumeration of the rational numbers [ i/j], for instance by taking the counter diagonals in

ad (iii) By theorem 1.2.5(i), the set of recursive reals is countable. The measure of a countable set of points on the real line is zero. Therefore, the measure of the set of all uncomputable reals is one. I.e., in the measure theoretic sense, ``almost all'' reals are uncomputable. This can be demonstrated by the following argument: Let M={ r_i} be an infinite point set (i.e., M is a set of points r_i) which is denumerable and which is the subset of a dense set. Then, for instance, every r_i Î M can be enclosed in the interval

Other denumerable point sets of reals are the rationals \Q and the algebraic reals. (Algebraic reals x satisfy some equation a₀xⁿ +a₁x^n-1+ ¼+a_n=0, where a_i Î \N and not all a_i's vanish.) Consequently, their measures vanish. The complement sets of irrationals \R - \Q and transcendentals (non algebraic reals) are thus of measure one [].

Despite such vague and probabilistic ideas as to ``pull out'' an arbitrary element of the ``continuum urn'' (you might have to assume the axiom of choice for doing that) which is then non recursive with probability one, it is hard to come up with a concrete elementary example of a provable non recursive real. One such example is the algorithmic halting probability W, which has been introduced by G. Chaitin [,] and which is even provable random, has been defined by equation (), p. (see also , p. ). Indeed, the algorithmic probability P(S), defined by equation (), p. , associated with an arbitrary recursively enumerable set S is provable non recursive.

Another ``example'' is a (binary) real r=0.r<sub>1</sub>r<sub>2</sub>r<sub>3</sub>¼ generated by infinitely many coin tosses of a fair coin and by identifying r<sub>i</sub>=0 or 1 for the outcome ``head'' or ``tail'' of the i'th coin toss, respectively. r is non recursive with probability one and recursive with vanishing probability.

1.2.6  Church-Turing thesis

Since the 1930's, other formal characterisations of functions corresponding to computational processes have been proposed (see again Rogers' book [], p. 18 for details). Probably the most prominent definition of recursive functions has been given by Alan Turing, who explicitly constructed a machine model (the Turing machine) to formalise the notion of computation. So far, all these definitions have turned out to be equivalent (i.e., there exist ``translations'' from one functional characterisation to another). We may therefore suspect that the class of the recursive functions defined above is inclusive enough to be a suitable characterisation of ``mechanical'' procedures; at least syntactically.

Likewise, a wide variety of functions, each agreed to be intuitively algorithmic, have been studied. Each one of these functions turned out to be a partial recursive function. The conjectural evidence of a connection between the informal, heuristic notion of effective computability and the precise notion of partial recursive function culminates in the Church-Turing thesis (sometimes referred to as ``Church thesis''): [Church-Turing thesis]   
Any algorithm corresponds to a partial recursive function. In other words: whatever is felt to be effectively computable can be brought within the scope of the class of partial recursive functions.

(Vice versa, by our understanding of ``mechanic'' computation, every partial recursive function corresponds to an algorithm. In other words: a (partial) recursive function is a mathematical entity which can be defined by an algorithm.

There is an equivalence between effectively computable algorithms and partial recursive functions.) The terms effectively computable, mechanically computable, computable and recursively enumerable will be used synonymously.

Remarks:

(i) The technical (methodological) importance of this equivalence is that proofs (sometimes referred to as ``proofs by Church's thesis'') can be carried through by convenient informal methods associated with algorithmics. At the same time, they have a concrete mathematical meaning, since, by the Church-Turing thesis, they refer to the class of partial recursive functions. Thereby, the formalised models of computation (such as the Turing machine) may remain ``on the shelf.'' Indeed, most proofs in this and later chapters will be ``proofs by Church's thesis.''

(ii) The nontrivial claim of the Church-Turing thesis is that every conceivable effectively computable process corresponds to a partial recursive function. The input corresponds to the function argument and the output corresponds to the function value. The converse statement relating recursive functions to effective computations is trivial, given our understanding of ``mechanic'' effective computation. In summary,

(iii) As has been already emphasized, the Church-Turing thesis includes a physical as well as a syntactic claim. In particular, it specifies which types of computations are physically realisable. As physical statements may change with time, so may our concept of effective computation.

1.2.7  Computation = polynomial equation

First we define the notion of diophantine equation: [Diophantine equation] 
A(n) polynomial (exponential) diophantine equation L(x₁,¼,x_n)=R(x₁,¼,x_n) is build up from non-negative integer variables x₁,¼,x_n and from non-integer constants by using the operation of addition A+B, multiplication A·B (and exponentiation A^B). An example for an exponential diophantine equation is aⁿ+bⁿ=cⁿ with a,b,c,n Î \N.

A predicate P(a₁,¼,a_n) is called recursively enumerable if there is an algorithm which, given the non-negative integers a₁,¼,a_n, will eventually, e.g., by generating a list of all n-touples satisfying P, discover that these numbers have the property P. P is recursive if, in addition to that, an algorithm exists which will eventually discover that these numbers do not have the property P.

The predicate P(a₁,¼,a_n) is called exponential / polynomial diophantine if P holds if and only if there exist non-negative integers x₁,¼,x_m such that

The following result is mentioned without proof; for a proof, see J. P. Jones and Y. V. Matijasevic [], which is reviewed G. Chaitin []. A predicate is polynomial / exponential diophantine if and only if it is recursively enumerable. By the Church-Turing thesis, the following equivalence holds: ``diophantine equation'' º ``effectively computable process.''

1.2.8  Recursively enumerable ¹ recursive

A set A Ì \N is called recursive if both A as well as its complement \N -A are recursively enumerable. We only mention here one important result of recursion theory. There exists a set A Ì \N which is recursively enumerable but not recursive. An example is the set of theorems of a ``sufficiently complex'' formal system arithmetic, or, equivalently, the outputs of ``sufficiently complex'' infinite computations. See also chapter on page . Furthermore, [Recursive inseparability] There exists a recursively inseparable pair of sets; i.e., A,B Ì \N such that

(i)

A and B are recursively enumerable;

(ii)

AÇB=Æ;

(iii)

there is no recursive set C with A Ì C and B Ì \N-C.

1.3  Universal computers

In section 1.5, p. pageref, the ``mechanic'' (in the computer sciences termed ``deterministic'') devices are followed by a specific, conceptually important non deterministic device called oracle. Oracles are capable of solving problems, such as the halting problem (see , p. ), which are recursively unsolvable. A ``model'' for an oracle problem solver will be given which, due to ``Zeno squeezing'' of its intrinsic time scale, may perform computations in the infinite time limit.

As has already been mentioned before, universal computation is invariant under changes of ``sufficiently complex'' machine models. In J. von Neumann's words (see Theory of Self-Reproducing Automata, ed. by A. W. Burks [], p. 50):

The importance of Turing's research is just this: that if you construct an automaton [[A]] right, then any additional requirements about the automaton can be handled by sufficiently elaborated instructions. This is only true if A is sufficiently complicated, if it has reached a certain minimum level of complexity. In other words, a simpler thing will never perform certain operations, no matter what instructions you give it; but there is a very definite finite point where an automaton of this complexity can, when given suitable instructions, do anything that can be done by automata at all.

Consider a set of instructions P of the type introduced for the definition of recursive functions. Assume further some particular listing of the set of instructions. Let P_x be the set of instructions associated with the Gödel number x=# (P_x) (for details, see 1.2.4, p. pageref). Let j_x stand for the function associated with P_x.

The following consideration yields an algorithmic definition of a universal algorithm and, by the Church-Turing thesis, of a universal recursive function u(x,y): given any two numbers x,y Î \N, find P_x, for instance by going through the enumeration of all sets of instructions until the (x+1)st place; then apply P_x to input y to calculate j_x(y). If j_x(y) gets an output, take this output value for u(x,y). Having done so, we have obtained an effectively computable algorithm (associated with u) which yields j_x(y) on inputs x,y. By this definition of u, u(x,y) effectively imitates any j_x(y). By the Church-Turing thesis, there exists a z Î \N, such that the algorithm u corresponds to the partial recursive function j_z(x,y). This can be stated as follows: [Existence of universal function]  
Assume arbitrary recursive functions j_x. Then there exists an index z and an associated universal partial function j_z(x,y)=u(x,y) such that for all x and y

One immediate consequence of this theorem is that there exists a critical degree of ``computational strength'' of the P's beyond which all further complexity can be absorbed into increased program size (i.e., algorithmic information), increased use of memory and increased computation time (i.e., computational complexity).

[Universal Computer] 
Any physical system or any device on which a universal function u=j_z can be implemented is called universal computer, or universal machine. A universal computer can compute all computable functions.

The notation U(p, s)=t will be used for a universal computer U with program p, input (string) s and output (string) t. Æ denotes the empty input or output (string). Furthermore, U(p,Æ)=U(p). Concatenation of programs and input/output strings is allowed. E.g., given two input strings s₁=s₁₁s₁₂s₁₃¼s_1i and s₂=s₂₁s₂₂s₂₃¼s_2j, a term denoted by ``s<sub>1</sub>,s<sub>2</sub>,'' or ``s₁s₂'' is treated by the automaton as the string s₁₁s₁₂s₁₃¼s_1is₂₁s₂₂s₂₃¼s_2j.

Examples

1.3.1  Turing Machine

There exist several examples of universal computers, all being fictious because no finite machine can be universal. The most prominent device is the Turing machine [,,] consisting of a finite memory unit and an infinite tape (which is tessellated into a sequence of squares) on which information is read or written. As has been noted before, A. Turing motivated the Turing Machine by the one-dimensional version of a sheet of paper on which arbitrary calculations can be performed according to ``usual rules.''

[Turing machine] Assume discrete time cycles, labelled by 0,1,2,¼. A Turing machine is an agency or automaton with the following features:

(i)

a finite number of internal states a₀,¼ ,a_k, which form a set A={ a_i}; a₀ is called the passive state, the other states a₁,¼, a_k are called active states;

(ii)

a linear, infinite tape, consisting of squares and extending to the right; the tape can be moved backward and forward through the machine so that at each moment only one square is scanned;

(iii)

each square is capable of having read or printed on it any one of a finite number of tape symbols s₀, s₁,¼,s_l; where s₀ is the blank symbol; so there are l+1 possible square conditions;

At each moment of time, the machine situation is defined by (i) a particular machine state a_i, by (ii) a particular position of the tape in the machine (i.e., which square is scanned), and (iii) by a particular printing of the whole tape.

In the active state, the Turing machine performs an act between the time t and t+1, consisting of three possible parts: (i) the writing of a tape symbol s_i¢ as the state of the square scanned at time t; subsequently accompanied by (ii) a tape shift, so that at the time t+1 the machine is either one square left of, or in the same, or one square right of the position scanned at t, denoted by L,C,R, respectively, and (iii) the choice of a new internal state a_j¢ for the next time cycle t+1. Any machine act can therefore be described by the triple s_i¢ {

The pair s_ia_j, or ij is called the machine configuration. The machine configuration determines the next act. If the configuration calls for a left move L but the scanned square is already the leftmost square of the tape, the machine goes into the passive state a₀. There are (l+1)k active configurations. A particular Turing Machine is therefore specified by a machine table, showing for each active machine configuration which act has to be performed. (A scheme of a Turing machine is drawn in Fig. 1.1.)

Example:

The following example is taken from St. C. Kleene's review article []. Consider the Turing machine specified by the machine table 1.1 with 11 internal states and two square symbols 0 for blank and 1 for s₁, respectively.

At time t=0, the Turing machine is in internal state 1 and scans the 3rd position of the tape, whose squares are in the states 0110 ¼ (``¼'' denotes blank states here). The time evolution of this machine is enumerated in table 1.2.

1.3.2  Cellular Automata

[Cellular Automaton]   
Assume discrete time cycles, labelled by 0,1,2,¼. A Cellular Automaton (CA) is an infinite collection of locally connected finite automata (cells) of the tessellated \Z^D, D Î \N. Let a_i,[n\vec](t) stand for the i'th internal state of the [n\vec]'th automaton (cell), [n\vec]=(n₁,n₂,¼, n_D), at time t. Let { [n\vec]} characterise the D-dimensional neighbourhood of [n\vec], including [n\vec], and let a_{i,{ [n\vec]}} (t) stand for the internal states of the automaton cells around [n\vec], including the origin [n\vec]. The internal state a_i,[n\vec](t+1) of the automaton at [n\vec] at time t+1 is given by a computable function f of the state and its neighbourhood states at time t, i.e.,

Remarks:

(i) Cellular Automata feature parallel processing, as opposed to the sequential Turing machine concept. Instead of the infinite tape, they operate with an infinite number of finite automata.

(ii) There exist several neighbourhood declarations, the most prominent ones being the von Neumann neighbourhood and the Moore neighbourhood, with 1+2D neighbours (including the centre) for D > 0 and 1+2D+2^D neighbours (including the centre) for D > 1, respectively. For D=2, they are drawn in Fig. 1.2. Another neighbourhood declaration is the Margolus neighbourhood, which is obtained by partitioning the cell array into finite, disjoint and uniformly arranged pieces (blocks), by block rules updating the block as a whole; and by a change of the partition with every time step (for details, see T. Toffoli and N. Margolus, Cellular Automata Machines [], chapter 12).

(iii) Universality of a specific CA in the sense of the Church-Turing thesis can be proved by embedding a Turing machine into a suitable Cellular Automaton structure [,,]. One particular ``fancy'' example, E. Fredkin's Billiard Ball Model [], mimics universal computation via the ``elastic scattering'' of CA ``billard balls''.

(iv) CA's perform optimally for physical configurations which can be decomposed into locally connected parallel entities. For more information and for recent developments, see T. Toffoli and N. Margolus, Cellular Automata Machines [], St. Wolfram's Theory and Application of Cellular Automata [] as well as references [,,]. For technical realisations, see, among others, references [,,].

1.3.3  Register machines

1.3.4  Digital computers are physical systems which are universal up to finite complexities

The statement that commercially available general-purpose computers are in some sense ``universal computers'' is quite obvious []. Otherwise they would not be very helpful for general algorithmic tasks, such as commercial applications, evaluation of particular functions (e.g., solutions of differential equations) and so on. It is, for instance, possible to simulate an arbitrary Turing machine with finite tape on them.

As available general-purpose computers are finite automata, i.e., as they are limited by the finiteness of memory size, tape length, runtime and virtually everything one can think of, they cannot compute all effectively computable algorithms. In terms of the Church-Turing thesis, the corresponding functional class is a subset of the recursive functions.

It is evident that tasks which are uncomputable on universal computers (such as the halting problem, see on p. ) cannot be solved on available general-purpose machines either. In this respect, they share some features with the fictious but truly universal abstractions, in particular with respect to undecidability.

1.4  Finite automata

Finite automata are computational devices which are finite in all of their features. They have a finite number of internal states, a finite number of input and output symbols, finite tape et cetera. Conceived as computational universes, they create environments which are more restricted than universal computers or, even more so, than oracles.

Every automaton is a universe of its own, with a specific ``flavour,'' if you like. Programmers may create ``cyberspaces'' (a synonym for automaton universes) of their imagination which are, to a certain extend, not limited by the exterior physical laws to which they and their hardware obey. Seen as isolated universes, some of these animations might have nothing in common with our physical world. Yet, others may serve as excellent playgrounds for the physicist.

Why should physicists investigate finite automata? There is a modest and a radical answer to this question. The modest finite automata thesis is this: There exist algorithmic features of automaton universes such as complementarity (see chapter , p. ) or undecidability (see chapter , p. ) which translate into physics and which are difficult to analyse by non algorithmic means.

The radical finite automata thesis is this: Because the physical universe actually is a finite automaton. This viewpoint has probably been most consequently put forward by E. Fredkin [] in the context of Cellular Automata. (Although a universal Cellular Automaton is no finite machine - it has infinite extension - its cell space is discrete, leaving room to only a finite, although ``very large,'' number of cells per unit volume element of whatever is considered as the fundamental scale.) The radical finite automaton thesis contains two claims, each of which should in principle be testable, at least to some extend: (i) the ``laws of nature'' are mechanistic; i.e., computable in the usual Church-Turing sense (although intrinsically there might not exist any effective procedure to find these laws and although forecasts corresponding to halting problems in general may not be computable); and (ii) under certain ``mild'' assumptions, the computational capacities of physical systems are finite. See also chapter 3, p. pageref for a discussion of related topics.

1.4.1  Definition

In the following, an automaton shall be characterised algebraically. For a more detailed treatment, see, among others, E. Moore's original article [], as well as the books by J. H. Conway [], J. E. Hopcroft & J. D. Ullman [], J. R. Büchi [] and W. Brauer []. Readers less interested in formal definitions may skip these sections. For them, it suffices to keep in mind that a (i,k,n)-automaton has i internal states, k input and n output symbols; it is characterised by its transition and output functions d and o. Two states are called distinguishable if there exists at least one experiment which distinguishes between them; i.e., which yields non identical output. Two automata are isomorphic if there exists a one-to-one translation between them and if corresponding output symbols are identical.

[k-algebra, (i,k,n)-automaton] A k-algebra A=(A,e,I,d) is a system consisting of

(i)

a set A={a₁,¼a_i}, corresponding to the internal states (finite automata have a finite number of internal states),

(ii)

an element e Î A, corresponding to the initial state,

(iii)

a set I={ s₁,s₂,s₃,¼, s_k}, corresponding to the k input symbols,

(iv)

a transition function d:A×I ® A, corresponding to a set of operators
{d₁,d₂,d₃,¼,d_k}, called transition operators.

A (i,k,n)-automaton A=(A,e,I,O,d,o) is a k-algebra A=(A,e,I,d) with

(v)

a set O={ t₁,t₂,t₃,¼, t_n}, corresponding to the n output symbols, and

(vi)

an output function o: A® O, mapping internal states into output symbols. O^* and I^* denote the set of all output and input sequences.

This type of an automaton is often called Moore automaton, since its output function o only depends on the internal state of the automaton. Another, more general automaton definition is the Mealy automaton, which is defined similarly to the Moore automaton, except that the output function o:A×I® O depends also on some particular input (instead of merely the internal automaton state). Whereas for the Moore automaton type one gets ``the first output free,'' any output from the Mealy automaton is obtained only after investment of one input symbol. If one discards the first output symbol from a Moore automaton, the class of Moore automata and the class of Mealy automata are equivalent; i.e., any Moore automaton can be translated into an isomorphic Mealy automaton and vice versa.

Any finite k-algebra can be represented by a transition table, with the present internal states enumerated in the first row, the input symbols enumerated in the first column and the future internal states in the remaining matrix. A finite (i,k,n)-automaton is additionally characterised by the output function. This function may be represented by an output table, listing all internal states (and the input symbols for Mealy-type automata) and their corresponding output symbol(s). A transition graph is obtained by drawing circles for every internal state and by drawing directed arrows to indicate the transition function on some input. For examples, see chapter , p. .

Transitions are indicated in the following way: let v Î A, then the transition from v with input i is vd_i. This notation translates into the standard notation. Let U denote a universal computer and p_A stand for the program which simulates a (i,k,n)-automaton on U, such that initially the (i,k,n)-automaton is in internal state e. Then U(p_A,s)=t, with the input sequences s generated by concatenation of input symbols s₁¼s_n, and with the output sequences t generated by concatenation of output symbols [t₀]t₁¼t_n ([t₀] is optional for Moore-type automata).

The ``halting state'' can be simulated by the introduction of a special state, say h. If the automaton is in this state, no input will cause it to leave that state.

1.4.2  Distinguishability of states

[Distinguishable internal states] Let w=s₁ s₂ ¼s_k be an input sequence (of length k), then let

An arbitrary number of states {a₁,a₂¼, a_i} are called distinguishable if and only if there exists at least one experiment performed on A of which the outcome depends on which one of these states the automaton was in at the beginning of the experiment.

An internal state a_i of an automaton A is called indistinguishable from a state a_j of A if and only if every experiment performed on A starting in the state a_i produces the same output as if it would start in state a_j. I.e., two states a_i and a_j are indistinguishable if and only if

1.5  Oracles

1.5.1  Definition

[Oracle (Turing [])] An oracle is some agent, or ``black box,'' which, upon being consulted, supplies the true (correct) answers about mathematical or algorithmic or physical entities. The ``magical insight'' characterises the non deterministic feature of oracles. The corresponding problem may or may not be decidable by any effective computation, the latter case being more interesting. An example for such a problem is the halting problem (for details see , p. ).

1.5.2  Zeno squeezing

A very similar setup has been introduced in Hermann Weyl's book Philosophy of Mathematics and Natural Science [], which has been discussed by A. Grünbaum in Philosophical Problems of Space and Time [], p. 630. H. Weyl raised the question whether it is kinematically feasible for a machine to carry out an infinite sequence of operations in finite time. H. Weyl writes ([], p. 42):

¼ Yet, if the segment of length 1 really consists of infinitely many sub-segments of length 1/2, 1/4, 1/8, ¼, as of `chopped-off' wholes, then it is incompatible with the character of the infinite as the `incompletable' that Achilles should have been able to traverse them all. If one admits this possibility, then there is no reason why a machine should not be capable of completing an infinite sequence of distinct acts of decision within a finite amount of time; say, by supplying the first result after 1/2 minute, the second after another 1/4 minute, the third 1/8 minute later than the second, etc. In this way it would be possible, provided the receptive power of the brain would function similarly, to achieve a traversal of all natural numbers and thereby a sure yes-or-no decision regarding any existential question about natural numbers! ¼

The argument is similar to a paradox which is often referred to as ``Achilles and the Tortoise,'' or ``Achilles and Hector,'' ascribed to Zeno of Elea (5th century B.C.). For a detailed treatment, see H. D. P. Lee's Zeno of Elea [], as well as G. S. Kirk's and J. E. Raven's The Presocratic Philosophers [], p. 292. It describes a race between Hector and Achilles as follows: for simplicity, assume that Hector is one unit of distance ahead of Achilles, and that Achilles runs twice as fast as Hector. Will Achilles ever catch up with and overtake Hector? Obviously not, if one argues as follows: Achilles runs to Hector's new position; however in the time that it took Achilles to run one unit of distance, Hector has advanced 1/2 unit of distance. Achilles runs to Hector's new position; however in the time that it took Achilles to run 1/2 unit of distance, Hector has advanced 1/4 unit of distance. Achilles runs to Hector's new position; however in the time that it took Achilles to run 1/4 unit of distance, Hector has advanced 1/8 unit of distance. ¼ ad infinitum. According to Aristotle in Physics Z9, Zeno seems to have argued that, by assuming infinite divisibility of space and time, one arrives at the conclusion that Achilles never catches up with Hector, which, given every-day experience that a faster body overtakes a slower one, is an absurd conclusion; Hence, if Zeno is interpreted correctly, he seems to have argued that infinite divisibility of space and time contradicts experience.

Zeno's argument has been formalised and interpreted in terms of undecidability by E. G. K. López-Escobar [] (see also E. W. Beth, The Foundations of Metamathematics [], p. 492). In a sense, Zeno may have anticipated Cantor's method of diagonalization: E. G. K. López-Escobar constructs an expression for the points successively reached by Achilles; then he constructs a new point, the ``meeting point'' of Achilles and Hector, for which this expression does not hold and which is nevertheless reached by Achilles. This contradicts the assumption that the expression describes the relative motion of Achilles and Hector completely. A sketch of the formal argument goes as follows: Let POS(r<sub>A</sub>(t),r<sub>H</sub>(t)) stand for the binary predicate that represents the simultaneous positions of Achilles r<sub>A</sub>(t) and Hector r<sub>H</sub>(t) at time t. The time will be measured discretely, i.e., t=0,1,2,¼ . As introduced here, the time parameter t is not Achilles' and Hector's ``proper time,'' but rather a ``squeezed'' time parameter. Intuitively speaking, the higher is t, the smaller is the amount of ``proper time'' corresponding to one unit of t-time (from t to t+1). In the limit of t® ¥, one unit of t-time corresponds to a ``proper time'' of measure zero. (For more details, see the oracle problem solver described below.)

Assume again that Hector is one unit of distance ahead of Achilles and that Achilles runs twice as fast as Hector. From the ``axiom''

Let us come back to the original goal: the construction of a ``Zeno squeezed oracle,'' or, in A. Grünbaum's terminology, of an ``infinity machine.'' It can be conceived as follows: Consider two time scales t and t.

(i) The proper time t measures the physical system time by clocks in a way similar to the usual operationalisations; whereas

(ii) a discrete cycle time t Î \N characterises a sort of ``intrinsic'' time scale for a process running on an otherwise universal machine.

For some unspecified reason we assume that this machine would allow us to ``squeeze'' its intrinsic time t with respect to the proper time t by a geometric progression. Let k < 1, then any time cycle of t, if measured in terms of t, is squeezed by a factor of k with respect to the foregoing time cycle (see Fig. 1.3), i.e.,

Picture Omitted

With such a device, countable many intractable and uncomputable problems, such as the halting problem, would become solvable. One could, for instance ``effectively compute'' the algorithmic halting probability W in the limit from below [cf. ref. [] and (), p. ] by identifying the time of computation with t. In the limit t® ¥, for k < 1 one obtains lim<sub>t® ¥</sub> w<sub>t</sub>=W at the finite proper time t < ¥. With such a Zeno squeezed oracle, many other problems would be within the reach of a ``constructive solution.'' Take, for instance, Fermat's conjecture, which could be ``(dis)proved'' by the following algorithm (in FORTRAN-style pseudocode):        DO LABEL1 a=1, 1, ¥;
       DO LABEL1 b=1, 1, ¥;
       DO LABEL1 c=1, 1, ¥;
       DO LABEL1 n=3, 1, ¥;
       IF a**n+b**n=c**n THEN PRINT (*,*) a,b,c,n;
                                   PRINT (*,*) `FERMAT WAS WRONG!!!'; STOP 1;
                     ELSE GOTO LABEL1;
       LABEL1: CONTINUE;
       PRINT (*,*) `FERMAT WAS RIGHT!!!'; STOP 2;
       END;

In the spirit of Zeno, the non existence of oracle problem solvers could be viewed as a further indication of the non existence of infinite divisibility. Indeed, it is not evident why such an oracle problem solver can be excluded in classical physics, e.g., in continuum mechanics. [This is related to infinite (measurement) precision in classical physics.] It is not completely unreasonable to put forward the provocative statement that, at least in principle, oracles of the above type are allowed in classical physics, and that classically the Church-Turing thesis 1.2.6, p. pageref, could be falsified by the actual construction of an oracle problem solver. (One might speculate that a simple process corresponding to diagonalization might cause the inconsistency of such a classical universe. The choice seems to be unlimited computational capacity versus consistency; cf. section , p. ).

1.6  Recursive analysis

A real number can be represented as a Cauchy sequence of rationals. Following Pour-El & Richards, a translation into recursion theory requires (i) a definition of a ``computable sequence of rationals,'' and (ii) a definition of ``effective convergence.'' [Computable sequence of rationals]  
A sequence { r_n} of rationals is computable if there exist three recursive functions a(n), b(n), c(n) from \N to \N such that b(n) ¹ 0 for all n and

Remarks:

(i) A complex number is computable if both its real and imaginary parts are computable; A vector is computable if each of its components is computable; a sequence { x_k } of real numbers is computable if all reals x_k are computable.

(ii) Let {x_k} and {y_k} be computable sequences of real numbers. Then the following sequences are computable: x_k±y_k, x_ky_k, x_k/y_k (y_k ¹ 0 "k), min (x_k,y_k), max(x_k,y_k), e^x_k, sinx_k, logx_k (x_k > 0 " k), ¼. These and similar results can be proven by Taylor series or other expansions which converge effectively.

(iii) Differentiation and integration can be properly reformulated in terms of recursion theory (for details see [], p. 33).

[Non recursive enumerability of the waiting time] 
Let a:\N ® A Ì \N be a one-to-one recursive function generating a recursively enumerable but non recursive set A. Let w(n) denote the waiting time, defined by

``Pedestrian versions'' of this statement and other important findings whose proofs are rather involved are listed below:

(i) There exist non computable reals corresponding to convergent sequences of computable rationals with non effective convergence. (C.f. G. Chaitin's W []; see also , p. .)

(ii) The maximum (minimum) value of a computable function is computable, but the point(s) where the maximum occurs need(s) not be (see, for instance, [], p. 42, and []). A necessary condition for this to occur is that there are infinitely many maximum (minimum) points. If a computable function takes on a local maximum (minimum) at an isolated point, then this point is computable.

(iii) Differential equations may have uncomputable solutions from computable initial values, but these solutions must be ``weak solutions'' in the sense of distributions. For the wave equation in 3+1 dimensions, that means that weak solutions are not even in C¹, the class of differentiable functions whose derivations are continuous ([], p. 73). Differential equations with computable initial values may also have uncomputable non unique solutions; see [] and G. Kreisel [].

(iv) Bounded linear operators in Banach space preserve computability, and unbounded operators do not ([], chapter 3).

(v) Under mild side conditions, a self-adjoint operator has computable eigenvalues, although the sequence of eigenvalues need not be computable ([], chapter 4).

The question still remains if ``pathologies'' such as non recursive solutions from evolution equations with recursive initial values have a physical meaning. Personally, the author believes that they seem to indicate the necessity for further restrictions of the class of solutions by physical assumptions, such as uniqueness, finiteness and continuity. This could be done on operational, on practical, on aesthetic and, in a broader sense, on metaphysical grounds. Yet, if the non recursive solutions are interpreted as physically meaningful, these solutions would correspond to physical events which would have been generated by a computer agent ``much more'' powerful than any universal computational device.

1.7  Formal systems correspond to computable processes

The (recorded) formalisation of theory began with Euclid and evolved to the concept of a formal (axiom) system, which will be introduced next. The goal is that, after specifying certain theoretical symbols, all relevant theoretical entities have to be expressed by axioms and rules of deduction. Then it should be possible to ``mechanically'' derive theorems by string processing or by other purely syntactic means. (In its extreme consequence, the program of formalisation can be understood as the ``elimination of the necessity of meaning and intuition.'') [Formal system] A formal system L is a system of symbols together with rules for employing them. The individual symbols are elements of an alphabet. Formulas are sequences of symbols. There shall be defined a class of formulas called well-formed formulas, and a class of well-formed formulas called axioms (there may be a finite or infinite number of axioms). Further, there shall be specified a list of rules, called rules of inference. If such a rule is called R, it defines the relation of immediate consequence by R between a set of well-formed formulas M₁,¼,M_k called premises, and a formula N called conclusion or theorem.

Examples of formal systems are the Peano axioms, Zermelo-Fraenkel set theory (with or without the axiom of choice), certain geometries et cetera.

The essence of inference, at least for a formalised theory, is string processing []. String processing can be performed by any (universal) computer. Conversely, any effectively computable process can be identified with some syntactic activity which is associated with ``inference.'' (Nothing needs to be said about the semantic aspect of such a formalism, such as the ``meaning'' of some string or of some process.)

Therefore, from a purely syntactic point of view, every effectively computable process U(p,s) can be identified with a formal system and vice versa. Indeed, as stated by K. Gödel in a Postscriptum, dated from June 3rd, 1964 ([], p. 369-370):

¼ due to A. M. Turing's work [[reference[]]], a precise and unquestionably adequate definition of the general concept of formal system can now be given, the existence of undecidable arithmetical propositions and the non-demonstrability of the consistency of a system in the same system can now be proved rigorously for every consistent formal system containing a certain amount of finitary number theory.

Turing's work gives an analysis of the concept of ``mechanical procedure'' (alias ``algorithm'' or ``computation procedure'' or ``finite combinatorial procedure''). This concept is shown to be equivalent with that of a ``Turing machine.'' A formal system can simply be defined to be any mechanical procedure for producing formulas, called provable formulas.

Let thus the ``input'' s of the computation correspond to ``axioms,'' the ``program'' p correspond to the ``rules of inference,'' and the ``output'' correspond to ``provable theorems,'' respectively (see table 2.2, p. pageref, for a translation of terminology). It should be stressed again that from the point of view of abstract coding and information theory, input and program are interchangeable, since, given a program p and a specific input s, it is always possible to write another program p¢ such that U(p¢,Æ)=U(p,s). One may object that computations may halt while one may derive theorems from the axioms of formal systems forever. This critique can be met by considering only computations which never halt. If a computation halts, it can be identified with a similar computation which differs from the original one only by the feature that instead of the halting mode it goes into an infinite loop with no output (i.e., by the substitution HALT ® LABEL 1: GO TO LABEL 2; LABEL 2: GO TO LABEL 1).

Another equivalence scheme between algorithms and formal systems has been introduced by G. Chaitin []. It again starts with the observation that one essential feature of formal systems is the existence of objective ``derivation'' rules, representable by some effective computation U¢(p,t), and (by the Church-Turing thesis) an associated recursive function which, applied to the axioms p, yields all theorems which can be derived from proofs with less than or equal to t characters length. In this scheme, the terms ``computer'' and ``rules of inference'', as well as ``program'' and ``axioms'', as well as ``output up to cycle time t'' and ``theorems with proof size £ t'' are synonyms. For fixed cycle times t, Chaitin's scheme and the above scheme can be brought into a one-to-one correspondence by recalling that for a universal computer C there exists a program q which simulates U¢ on U and an input (p,t) such that U¢(p,t)=U(q,(p,t)) for all p and t.

Chapter 2
Mechanism and determinism

With recursion theory being a relatively young discipline, the notion of ``physical determinism'' in classical physics lets unspecified the exact recursion theoretic status of the physical entities. In this chapter, such a specification is attempted, re-interpreting the classical meaning recursion-theoretically. It is not unreasonable to assume that a recursive evolution seems to be ``at the heart'' of the classical notion of ``determinism.'' Usually, these evolution functions are defined on continua, such as \R<sup>n</sup>. In particular, the initial values and the solutions are defined in \R<sup>n</sup>. Yet, by theorem 1.2.5, p. pageref, ``almost all'' elements of the continuum are uncomputable. In particular, the assumption of an exact (i.e., effectively computable) description of the initial value(s) becomes ridiculed.

``Strong determinism'' or what henceforth will be called ``mechanism'' could alternatively be understood as a synonym for ``total causality,'' which might be translated into the language of recursion theory by ``total computability,'' or ``computability in all aspects.'' (For a philosophical treatment of this and related topics, see for instance Ph. Frank, Das Kausalgesetz und seine Grenzen [].) This should not be confused with the above requirement of a recursive evolution. It is a nontrivial substitution, since it requires all theoretical entities to be effectively computable.

For example, classical continuum physics is ``deterministic'' but not ``mechanistic'' in the above sense, since its evolution equations are computable, whereas its domain is the continuum. Here one could resort to the notion of ``arbitrary but finite accuracy parameter values,'' or ``finitely computable parameter values.'' Since finite numbers are recursively enumerable, this would restore effective computability.

Therefore, in what follows (if not denoted otherwise) the term ``deterministic'' refers to merely an effectively computable evolution function, whereas a system which is totally computable in all of its aspects is called ``mechanistic.'' In a way, this is a translation of Laplace's demon into the language of recursion theory. [Deterministic, mechanistic theory] 
A deterministic theory has an evolution function which is effectively computable / recursive.

A mechanistic theory is effectively computable / recursive in total. I.e., all theoretical entities are effectively computable / recursive. In particular, all initial values, laws and solutions of a mechanistic theory are recursively enumerable.

The terminology ``mechanistic'' is due to G. Kreisel []. According to G. Kreisel, a theory is mechanistic

if every sequence of natural numbers or every real number which is well defined (observable) according to the theory [[is]] recursive or, more generally, recursive in the data.

Further Remarks:

(i) Physical determinism in the defined sense does not imply that the initial and/or the solution (the final state) can be represented by an effective computation.

(ii) As has been pointed out before, computability of the equation of motion and the initial value does not guarantee computability of the solution, at least not if the solution is non unique [], if it is obtained by unbounded linear operators ([], chapter 3), or if its a weak solution ([], p. 73). For mechanistic theories, uncomputable solutions from computable initial values and computable equations of motions are excluded by definition.

(iii) Since, from the point of view of coding and information theory, the distinction between the ``evolution'' and ``initial value'' (i.e., some algorithm and its input) is rather arbitrary, the above distinction between ``determinism'' and ``mechanism'' is rather arbitrary. A more radical but clearer distinction would be between non recursive and recursive (``mechanistic'') theories.

(iv) Uncomputability does not imply randomness (see chapter p. ).

Table 2.1 summarises the computational aspects of physical theories.

By identifying the evolution functions of mechanistic physics with the partial recursive functions, one obtains a correspondence which can be represented in table 2.2 (The table includes an extension to formal systems). The term correspondence between structures in physics, algorithmics and mathematics should be understood as a one-to-one translation between such structures, which become identical if only their elements are renamed. Note that, technically speaking, a mechanistic physical system should be perceived as a never-ending computational process. Such an algorithm which does not halt could alternatively be viewed as a continuing derivation of theorems of a formal system,

Table 2.3 gives a brief overview of the algorithmic features of physical theories.

Chapter 3
Discrete physics

All previously introduced models of computation have been discrete in the sense that the processes involved are discontinuous with respect to space and time, storage capacity, program length and so on. Effective computations can be decomposed into distinct parts; e.g., execution steps. Any algorithmic model of a physical system inherits this feature. Discreteness is opposed to the assumption of continuity by classical physics.

In what follows, several features of discrete versus continuous models of motion and evolution will be discussed, partly by taking up the arguments of Zeno of Elea (5th century B.C.) on motion. For further considerations and references, see H. D. P. Lee's Zeno of Elea [] and A. Grünbaum's Modern Science and Zeno's paradoxes [] and Philosophical Problems of Space of Time, Second, enlarged edition, p. 159; Ibid., p. 808 [].

The arguments will be phrased in terms of Cellular Automaton models. This can be done without loss of generality as long as the context is universal computation. The same holds for discretization of space-time versus discretization of other variables; e.g., action-angle. For any universal computer can simulate any other universal computer, the only difference being the complexities required for one system to simulate the other.

3.1  Infinite divisibility and continuity

In what is now often referred to as the paradox of ``dichotomy,'' Zeno argues that (in Simplicius' interpretation, quoted from [], p. 45) if space is infinitely divisible, and if

``¼ there is motion, it is possible in a finite time to traverse an infinite number of positions, making an infinite number of contacts one by one; but this is impossible, and therefore there is no motion.''

A ``resolution'' of this kind of paradox can be obtained by assuming an infinite divisibility not only of space but also of time. I.e., one finite (proper) time interval can be divided into an infinitely many time steps in such a way that a body in motion traverses an infinite number of positions, making an infinite number of contacts, one position by one time step. A proper formalisation of this resolution can be expressed in terms of analysis. For further discussions along different lines see A. Grünbaum [,].

Yet, as this resolution (and even constructive analysis []) operates by dividing space-time into infinitely many subdivisions, finite processes of computation are insufficient models of the situation. Recall Zeno's argument, p. pageref. If one actually wants to simulate, for instance, successive positions of ``Achilles and the Tortoise,'' one may start by giving the following table:

Stated differently, by assuming infinite divisibility of space and time, an infinity of space-time points is approached by Achilles' and the Tortoise's body on a step-by-step basis in finite proper time and space. This would require a capacity of the system to compute ``the limit'' (of infinitely small space and time scales).

It is not completely unreasonable to speculate that in some way or another, this capacity of a physical system to compute these limits could be utilised; e.g., for the construction of an oracle which might be able to solve the halting problem. (For details, see p. pageref.) This would require a dramatic revision of our concept of ``effective'' or ``mechanic'' computation in the way discussed in chapter 1. - Oracle computation by continuous systems might be seen as one aspect of the fact that they do not correspond to any process of effective computation.

If one excludes limit computations of the above kind, one has to explain why. It is to be expected that an explicit statement of exclusion will effectively render a discrete mathematical model of motion, as it is discussed below. This may be seen as a translation of Zeno's paradoxes of ``dichotomy'' and ``Achilles and the Tortoise'' into a more contemporary form; using terminology from continuum physics and recursion theory.

3.2  Finite divisibility and discreteness

In the paradox of the ``arrow,'' according to Aristotle [Phys. Z 9], Zeno argues as follows ([], p. 53):

¼ For if, he says, everything is either at rest or in motion, but nothing is in motion when it occupies a space equal to itself, and what is in flight is always at any given instant occupying a space equal to itself, then the flying arrow is motionless.
¼
This conclusion follows from the assumption that time is composed of instants.

One concretion of the assumption that time is composed of instants or atomic ``nows'' is the requirement that time is discrete. Assume for the moment that space is discrete as well.

Motion in a discrete space-time can be realised by Cellular Automata. For a vision of Cellular Automaton models for space-time, see for instance, the articles Digital Mechanics by E. Fredkin [], Cellular Vacuum by M. Minsky [] and the book Cellular Automata Machines by T. Toffoli and N. Margolus []. In what follows, one-dimensional Cellular Automaton models of arrow motion are discussed.

The simplest arrow motion can be realised by a right shift; i.e., given a cell with its surrounding two neighbours, the transition rule {l,X,X}® l (X stands for any state) yields the state l as the next value for the center state. Let the initial state be ``¼ ->____________ ¼.'' Then, the time evolution is given by (see p. for a Mathematica program simulating this evolution):

... --->_________________________________________________________ ...
... _--->________________________________________________________ ...
... __--->_______________________________________________________ ...
... ___--->______________________________________________________ ...
... ____--->_____________________________________________________ ...
... _____--->____________________________________________________ ...
... ______--->___________________________________________________ ...
... _______--->__________________________________________________ ...
... ________--->_________________________________________________ ...
... _________--->________________________________________________ ...
... __________--->_______________________________________________ ...
... ___________--->______________________________________________ ...
... ____________--->_____________________________________________ ...
... _____________--->____________________________________________ ...
... ______________--->___________________________________________ ...
... _______________--->__________________________________________ ...
... ________________--->_________________________________________ ...
... _________________--->________________________________________ ...
... __________________--->_______________________________________ ...
       .
       .
       .
 

The velocity of the arrow is 1 cell per cycle time, independent of the length of the arrow. A less trivial example can be found in M. Minsky []. There, the transition rule is given by {-,-, > }® > ,  {X,-, > }® X,  {X, > , > }® *,  {*,X,X}® > ,  {*, > ,X}® *,  {X,*,X}®- (X stands for any state). An arrow in this cellular array propagates with a velocity which depends on its length. E.g., for an arrow of length 3,4,5 and 6 cells, the velocity is 1 cell per 5,8,9 and 11 cycles, respectively. Explicitly,

 ... ->__________________________________________________________ ...
 ... ->>__________________________________________________________ ...
 ... _>>__________________________________________________________ ...
 ... _*>__________________________________________________________ ...
 ... _-*__________________________________________________________ ...
 ... _->_________________________________________________________ ...
 ... _->>_________________________________________________________ ...
 ... __>>_________________________________________________________ ...
 ... __*>_________________________________________________________ ...
 ... __-*_________________________________________________________ ...
 ... __->________________________________________________________ ...
 ... __->>________________________________________________________ ...
 ... ___>>________________________________________________________ ...
 ... ___*>________________________________________________________ ...
 ... ___-*________________________________________________________ ...
 ... ___->_______________________________________________________ ...
 ... ___->>_______________________________________________________ ...
 ... ____>>_______________________________________________________ ...
 ... ____*>_______________________________________________________ ...
       .
       .
       .
  (period 5)


 ... --->________________________________________________________ ...
 ... --->>________________________________________________________ ...
 ... ->>>________________________________________________________ ...
 ... ->>>>________________________________________________________ ...
 ... _>>>>________________________________________________________ ...
 ... _*>>>________________________________________________________ ...
 ... _-*>>________________________________________________________ ...
 ... _-*>________________________________________________________ ...
 ... _---*________________________________________________________ ...
 ... _--->_______________________________________________________ ...
 ... _--->>_______________________________________________________ ...
 ... _->>>_______________________________________________________ ...
 ... _->>>>_______________________________________________________ ...
 ... __>>>>_______________________________________________________ ...
 ... __*>>>_______________________________________________________ ...
 ... __-*>>_______________________________________________________ ...
 ... __-*>_______________________________________________________ ...
 ... __---*_______________________________________________________ ...
 ... __--->______________________________________________________ ...
       .
       .
       .
  (period 9)

 ... ---->_______________________________________________________ ...
 ... --->>_______________________________________________________ ...
 ... --->>>_______________________________________________________ ...
 ... ->>>>_______________________________________________________ ...
 ... ->>>>>_______________________________________________________ ...
 ... _>>>>>_______________________________________________________ ...
 ... _*>>>>_______________________________________________________ ...
 ... _-*>>>_______________________________________________________ ...
 ... _-*>>_______________________________________________________ ...
 ... _---*>_______________________________________________________ ...
 ... _---*_______________________________________________________ ...
 ... _---->______________________________________________________ ...
 ... _--->>______________________________________________________ ...
 ... _--->>>______________________________________________________ ...
 ... _->>>>______________________________________________________ ...
 ... _->>>>>______________________________________________________ ...
 ... __>>>>>______________________________________________________ ...
 ... __*>>>>______________________________________________________ ...
 ... __-*>>>______________________________________________________ ...
       .
       .
       .
  (period 11)
 

One could speculate that, if the motion of a body in the physical vacuum can be described similarly, then there is a remote possibility to increase this velocity by proper algorithmic manipulations; e.g., by re-programming the vacuum motion or by re-shaping the body.

There is an obvious contradiction with Zeno's argument: in the listed Cellular Automaton configurations the arrow in flight occupies a cell region equal to its size, and yet it moves. This may be explained from different perspectives.

One may argue that the shape of the arrow (i.e., the initial state) and the transition rules contain information about the evolution; such that any ``snapshot'' of the position of the arrow should be accompanied by another quantity called ``momentum,'' which completes a description of the arrow's motion. In this way, phase space is introduced.

Another explanation would be that the shape of the arrow (i.e., the initial state) and the transition rules contain ``hidden'' information about the evolution which reveals itself after successive time periods. This argument somewhat resembles the construction of a reversible second-order system (computation) proposed by E. Fredkin ([], p. 141) by

3.3  Simultaneity

In the paradox of the ``stadium,'' Zeno argues that an attempt to define space and time distances by the motion of rigid bodies results in a contradiction. Assume again that space and time are uniformly partitioned into cells and instants (time cycles). Consider identical bodies marked by

This argument is somewhat similar to A. Einstein's critique of the classical notion of simultaneity put forward in relativity theory, resulting in a transformation of space and time scales []. In discrete physics, any velocity will be characterised by rationals, the ``natural'' extrinsic unit being one cell per cycle time. Without loss of generality it is assumed that the maximal velocity a body can move is one cell per cycle time, denoted by c. In analogy to relativity theory, this velocity is used to define synchronised events. Flows of this kind will be called rays.

The synchronisation convention of two clocks at two points A and B can be adopted from relativity theory ([], p. 892): [Einstein synchronisation []] Assume two clocks at two arbitrary points A and B which are ``of similar kind.'' At some arbitrary A-time t_A a ray goes from A to B. At B it is instantly (without delay) reflected at B-time t_B and reaches A again at A-time t_A¢. The clocks in A and B are synchronised if

The two-ways ray velocity is given by

It is identical for all frames, irrespective of whether they are moving with respect to the rest frame of the cellular space or not.

Example:

Synchronisation by ray exchange can be simulated on a Cellular Automaton using the following rules for inertial arrow motion (X stands for any state): { > ,_,X} ® > , {X,_, < } ® < , {_,_,_} ® _ , {X,_, > } ® _ , { < ,_,X} ® _ , {_, > ,_} ® _ , {_, < ,_} ® _ and for reflection (rigid mirror I): {X, > ,I} ® < , {I, < ,X} ® > , {X,I,X} ® I , {_,_,I} ® _ , {I,_,_} ® _ , {I, > ,_} ® _ , {_, < ,I} ® _. (The evolution can, for instance, be realised by the Mathematica program on p. .) With two rigid mirrors at A and B spaced 7 cells apart, the evolution is given by

                         A       B

... _____________________I>______I______________________________ ...
... _____________________I_>_____I______________________________ ...
... _____________________I__>____I______________________________ ...
... _____________________I___>___I______________________________ ...
... _____________________I____>__I______________________________ ...
... _____________________I_____>_I______________________________ ...
... _____________________I______>I______________________________ ...
... _____________________I______<I______________________________ ...
... _____________________I_____<_I______________________________ ...
... _____________________I____<__I______________________________ ...
... _____________________I___<___I______________________________ ...
... _____________________I__<____I______________________________ ...
... _____________________I_<_____I______________________________ ...
... _____________________I<______I______________________________ ...
... _____________________I>______I______________________________ ...
... _____________________I_>_____I______________________________ ...
... _____________________I__>____I______________________________ ...
... _____________________I___>___I______________________________ ...
... _____________________I____>__I______________________________ ...
... _____________________I_____>_I______________________________ ...
... _____________________I______>I______________________________ ...
... _____________________I______<I______________________________ ...
... _____________________I_____<_I______________________________ ...
... _____________________I____<__I______________________________ ...
... _____________________I___<___I______________________________ ...
... _____________________I__<____I______________________________ ...
    .
    .
    .
 

Synchronisation can be defined in all frames, irrespective of whether they are moving with respect to the cell space or not. However, it cannot be expected that two frames which are in motion against each other have identical synchronisations. Indeed, the assumption of identical synchronisations yields a contradiction. Consider the following Gedankenexperiment, which is again due to Einstein ([], p. 895): Let the points A and B be the endpoints of a rigid rod. Assume that the rod is moving with constant velocity with respect to the cellular space. Assume four observers; two observers travelling with the rod at points A and B, and two observers in the rest frame of the cellular space. The latter observers synchronise their clocks and measure the length [`AB] of the moving rod in the rest frame of the cellular space (at equal rest frame times). Assume further that if two events are synchronised in the rest frame of the cellular space, then they are synchronised in the rest frame of the moving rod (wrong). An attempt to verify the synchronisation of the clocks in the moving frame yields to a refusal, since if the array is first emitted in the direction of motion and reflected afterwards, then

Of course, one could define a global time synchronisation; for instance by counting the number of cycle times of the array. This view, however, is an extrinsic (see below) view, which yields a preferred frame of reference, the frame at rest with respect to the cellular space. Such a definition is an alternative to the above definition of synchronisation given by Einstein. Einstein synchronisation is suitable for an intrinsic (see below) definition. It does not operate with a preferred frame of reference; the ``ideological preference'' being the relativity principle (symmetry). The according time will sometimes also be called intrinsic time. Intrinsic time is discrete. But, just as in relativity theory, for moving frames the elementary unit of intrinsic cycle time becomes dilatated. By a similar argument, the elementary unit of length becomes dilatated.

How far can one go to reconstruct relativity theory? Not very far if one does not take into account dispersion (e.g., the energy-momentum relation) and other dynamical features. Because even for relativistic kinematics, an alternative synchronisation could be defined by signals of arbitrary velocity or by defining a preferred frame of reference, such as the one at rest with respect to the cosmic background blackbody radiation. The physical content of Einstein synchronisation is the absence of any criterion by which one inertial frame might be preferred over the other. This is not the case for a cellular array, where - at least extrinsically - a preferred frame is the frame at rest with respect to the cellular array. Whether this preference holds for intrinsic perception is questionable.

Stated differently, one criterion for Einstein synchronisation is the invariance of the physical laws, such as electromagnetism, in arbitrary inertial frames. This is one reason why, for instance, synchronisation by sound is no good if one attempts to describe physical motion governed by electromagnetism. A detailed discussion of related topics is given in [,,], where it is argued that, depending on dispersion relations, creatures in a ``dispersive medium'' would develop a theory of coordinate transformation very similar to relativity theory.

Chapter 4
Source coding

Physical entities such as experimental measurement results, time series et cetera as well as physical theories can be symbolically treated on an equal footing - as an information source of symbols. (The notion of the term ``symbol'' remains intuitive, since any definition of ``symbol'' has to be done in terms of symbols.)

The first sections are devoted to general source coding schemes, which have been developed in the context of the foundations of quantum mechanics [,] and for the coding of time series, which has been introduced as symbolic dynamics []. We then consider the Gödel numbering of axiomatised physical theories. For a more detailed account, see, for instance, R. W. Hamming's book Coding and Information Theory [], R. J. McEliece, The Theory of Information and Coding [], or R. Ash, Information Theory [].

4.1  General source coding

[System] A system is anything on which experiments can be performed.

Examples:

(i) Any finite deterministic automaton is a system. For instance, your PC / workstation (insert your favourite brand here:) ``¼'' is a system. Another example is the Moore automaton defined on p. .

(ii) Any mechanical or quantum device is a system.

(iii) The great beyond is no system, unless one succeeds to perform experiments on it. This statement needs not be entirely ridiculous, because what is called the great beyond depends on scientific knowledge and believes which transform(s) in history. For instance, what is presently called ``electromagnetic phenomena'' was mostly obscure and beyond anybody's experimental limits only 300 years ago.

[Experiment, manual, outcome, event]  
A physical system is characterised by experiments performed on it. The collection of all experiments \M is called manual or propositional calculus.

The i'th experiment will be denoted by e_i. Any experiment can be decomposed into elementary TRUE- FALSE-experiments, called propositions and denoted by e_ij.

The members of an experiment are called outcomes. Associated with every proposition e_ij are the two elementary outcomes TRUE and FALSE.

An event p_i Ì \M is a subset of an experiment e_i, associated with particular outcome(s). In terms of elementary experiments, p_ij corresponds to the jth experiment e_ij of e_i. Every event is also called element of physical reality.

Remarks:

(i) Fig. 4.1 shows the hierarchy ``manual ® experiment ® outcome ® event'' of perception defined by 4.1.

Picture Omitted

(ii) The terminology manual suggests a collection or catalogue of events. It defines an empirical universe and represents the ``admissible'' elements of physical reality; insofar the manual is the physical primitive.

(iii) It is easiest to imagine an empirical universe consisting of propositions, i.e., statements which are either TRUE or FALSE (see the following example).

(iv) Throughout this book a notion of element of physical reality is used which refers only to outcomes of actual measurements. This concept is more restricted than the EPR-terminology []:

``If, without in any way disturbing a system, we can predict [[!]] with certainty (i.e., with probability equal to unity) the value of a physical quantity, then there exists an element of physical reality corresponding to this quantity.''

Example:

Consider an automaton consisting of i internal states labelled by numbers 1 £ k £ i. Assume that all internal states can, informally speaking, be ``experimentally distinguished'' (for a definition, see chapter 1.4.2, p. pageref). Then, statements of the form ``the automaton is in state k,'' 1 £ k £ i, are propositions. The manual is the union of propositions. The possible experimental outcomes are TRUE and FALSE, respectively. After performing an actual experiment, an event is defined by one of these values. If defined, propositions can be constructed with logical ``or'' and ``and'' or ``not'' operations.

[Coding] 
Let È_j=1^M p_ij = p_i be an event, decomposed into elementary events p_ij. For elementary events, the source alphabet consists of just two symbols s₁ and s₂, corresponding to TRUE and FALSE, respectively. The code # ( p_ij) of p_ij is thus defined by

Remarks:

(i) if one identifies s₁=0 and s₂=1, the event p_i can be coded as a binary rational number as follows:

(ii) Note that, instead of taking some (natural) numbers as symbols, one could have taken any other entity which could be identified as symbol, such as the letters of the English or Greek alphabet, or apples & oranges et cetera.

(iii) So far we have not dealt with the translation of these source code symbols into an alphabet which is algorithmically recognisable by some computable process. This is discussed in the section on encoding, p. . For information sources with source alphabet s₁,s₂,¼, s_q with q symbols, the generalisation to radix ³ q notation is straightforward. If the code alphabet consists of less symbols than the source alphabet, then more sophisticated encoding techniques are necessary. These will be discussed below.

(iv) For technical reasons it often will be assumed that with any number p occurring in the system also ``elementary functions'' (recursive functions) g(p) thereof are codable within the system. This is equivalent to postulating the existence of a universal computer in the system.

(v) If the context is unambiguous, the code signs ``# (   )'' can be dropped. Any event p_i is then written as p_i=0.p_i1p_i2p_i3¼p_in.

(vi) For fractal source coding, see section , p. .

4.2  Symbolic dynamics

A partition x = { E₁,¼,E_q} is a set of subsets of X such that

[Sequence of pointer readings] 
To every E_i Î x, associate a pointer reading sⁱ. A sequence of n pointer readings, representing experimental outcomes, is denoted by

Notice that superscripts are used to denote the i'th symbol sⁱ, whereas subscripts are used to denote the place of the symbol in the sequence of pointer readings Y. The sⁱ's in Y are characters of an arbitrary alphabet S with q symbols. (This motivates the view of Y as a word, which is the starting point of linguistic analysis, in particular with respect to the Chomsky hierarchy of languages [].)

The terminology of symbolic dynamics is related to the general coding scheme: identify a time sequence Y obtained from a restricted alphabet S={ 0,1} with a particular event, say p_i, by setting s_j=p_ij.

4.3  Coding physical theories

Syntactically, any physical theory is representable by symbols. (Let us, for the moment, disregard the semantic content of a theory, i.e., its ``meaning'' et cetera.) These symbols can be ``read'' by some ``observer'' or agent by performing a series of experiments. Examples are the sensory perceptions associated with the reading of a book on theoretical physics, or the reading of a computer tape containing an effective procedure for solving an evolution equation et cetera; more generally, by experimentally observing some representations of theories. E.g., the reading of the term ``E=mc²'' can be seen as an optical scanning experiment which yields the (successive) events ``E,'' ``=,'' ``m,'' ``c'' and ``².''

These symbols may be interpreted as input for some effective computation producing ``predictions.'' In what follows, we assume that physical theories are mechanistic, i.e., that they can be represented by an algorithm.<sup>1</sup> For the time being, no attention is thus paid to theories which cannot be brought into such a form, as well as to the question, ``how can such theories be created?''

The enumeration of programs discussed in section 1.2.4, p. pageref, can be used to generate a unique code of such a theory. An alternative would be the use of instantaneous (prefix) codes for entities of formal systems; see section , p. . Still another (probably not very practical) coding scheme is Gödel's original construction of Gödel numbers, for which Gödel uses the uniqueness of prime factors of whole numbers. The following definition deals with a very particular language (alphabet), which is appropriate for the task of deriving the incompleteness theorems []; a generalisation to more general languages (alphabets) is straightforward. [Gödel numbers]  
Assume an alphabet consisting of the symbols (, ), ~ ,® , ", variables x_k, constants a_k, functions f_kⁿ and relations A_kⁿ. It is possible to map terms containing these symbols injectively onto the odd, positive integers by the Gödel number function #: # (()=3; # ())=5; # (,)=7;# ( ~ )=9; # (®)=11; # (")=13; # (x_k)=7+8k; # (a_k)=9+8k;# (f_kⁿ)=11+8×(2ⁿ×2^k); # (A_kⁿ)=13+8×(2ⁿ×3^k).

Every well-formed formula F=s₁¼s_k consisting of the symbols of the alphabet, functions and relations can be injectively mapped via

Every deductive proof consists of a sequence of well-formed formulas F₁¼F_k can be uniquely mapped via

In a binary Gödel numbering of the type just introduced, the axioms of a theory can be coded in bit strings (for instance by rewriting the values # (F) in binary notation). All such bit strings can be merged in a single finite bit string. This string is the object of investigation if one is interested in the algorithmic information content of a theory (see and , p. , ). The rules of inference can then be envisioned as a computable algorithm for enumerating the bit strings corresponding to provable theorems from the axiom bit string (for details, see table 2.2, p. pageref).

Chapter 5
Lattice theory

5.1  Relations

[Relation, equivalence relation]  
Assume two sets M,N. Every subset of the Cartesian product M×N is a (binary) relation fRg, f Î M, g Î N. There are as many relations as there are subsets of M×N.
Let M=N. An equivalence relation satisfies the following properties:

(i)

fRf for all f Î M (reflexivity);

(ii)

fRg Þ gRf for all pairs f,g Î M ( symmetry);

(iii)

fRg and gRh Þ fRh for all f,g,h Î M (transitivity).

[Equivalence class, quotient] The subset f^R={ g | fRg} is called the equivalence class of f modulo R.

The set M/R={f^R | f Î M}, consisting of all equivalence classes modulo R is called the quotient of M by R. R yields a partitioning of M.

Every equivalence relation R corresponds to a function j such that j(f)=f^R for all f Î f^R. Conversely, to every function j:M® N corresponds an equivalence relation `` º _j '' on M, defined by

The elements in M/ º _j , the quotient of M by º _j , correspond one-to-one to elements of N. This amounts to renaming the elements of N by elements of the quotient M/ º _j . One can thus define a map

In general, an isomorphism between two algebraic structures (admitting certain ``similar'' operations) is a one-to-one element-to-element correspondence which preserves all combinations. The following definition specifies the operation to (binary) relations. [Isomorphism, automorphism] Let M<sub>1</sub> be an algebraic structure with a (binary) relation R<sub>1</sub> and let M<sub>2</sub> be another algebraic structure with a (binary) relation R<sub>2</sub>. An isomorphism @ is a relation defined by a one-to-one map (``translation'') I from M₁ into M₂ which preserves the relations, i.e., M₁ @ M₂ with a one-to-one map I satisfying

If M₁=M₂, then @ is called an automorphism.

Remarks:

(i) Informally, the concept of an isomorphism is that two algebraic structures ``look much the same'' and become identical if only their entities are renamed.

(ii) An isomorphism defines an equivalence relation.

5.2  Partial order relation

[Partial ordering, poset] A partially ordered set (poset) is a system M in which a binary order relation ``\im'' (inverse ``\fo'') is defined, which satisfies

(i)

f\im f, for all f Î M (reflexivity);

(ii)

f\im g and g\im hÞ f\im h (transitivity);

(iii)

f\im g and g\im fÞ f=g (identitivity).

The ``immediate superiority'' of f with respect to g will be defined next. By ``f covers g,'' it is meant that f\im g and that f\im x\im g is not satisfied by any x Î M, x ¹ f, x ¹ g.

Any finite partially ordered set M can be conveniently represented graphically by a Hasse diagram in the following way. [Hasse diagram] Let M be a partially ordered set. The Hasse diagram of M is a directed graph obtained by drawing small filled circles representing the elements of M, so that f is higher than g whenever f\im g. A segment is then drawn from f to g whenever f covers g.

Remarks:

(i) As the direction is always from the bottom to the top, Hasse diagrams are drawn undirected.

(ii) Any finite partially ordered set is defined up to isomorphism by its Hasse diagram. I.e., two isomorphic partially ordered sets must have a one-to-one relation between their highest & lowest elements, between elements just above lowest elements, and so on; corresponding elements must be covered equally.

[Linearly ordered set] If for all elements f,g of a partially ordered set M either the relation ``f\im g'' or the relation ``g\im f'' is satisfied, M is called a linearly ordered set.

[Chain] A chain in a partially ordered set M is a subset N Ì M which is a linearly ordered set.

[Length] Let N be a chain of a partially ordered set M. The length |N| of N is the cardinal number (i.e., the number of elements) of N. The length of the partially ordered set |M | is the supremum over the length of all chains in M minus 1. M has finite length if M < ¥.

[Atom,coatom] Assume a partially ordered set with a least element 0 and a greatest element 1.

(i)

Atoms are elements which cover the least element 0.

(ii)

Coatoms are elements which are covered by the greatest element 1.

(iii)

The partially ordered set is atomic if every a ¹ 0 in it is greater than or equal to an atom.

Examples:

(i) Fig. 5.1(a) shows the Hasse diagram of a linearly ordered set. Fig. 5.1(b) shows the Hasse diagram of a non linearly ordered set.

(ii) Figs. 5.1(a)& (b) show the Hasse diagrams of atomic sets. Fig. 5.1(c) shows the Hasse diagram of a non atomic set.

Next the lattice concept will be introduced.

5.3  Lattice

Lattice theory is the theory of partially ordered sets with the property that two arbitrary elements have a common upper and lower bound. It provides a ``generic'' framework for the investigation of important algebraic structures occurring, for instance, in Hilbert space theory and logic. [Lattice, version I] A partially ordered system \L = (\L , \fo ) with order relation ``\fo'' (inverse ``\im'') is a lattice if and only if any pair f,g of its elements has

(i)

a meet or (greatest) lower bound [infimum] inf (f,g) such that

inf(f,g) \fo f

inf(f,g) \fo g

h\fo f and h\fo g imply h\fo inf(f, g);

(ii)

and a join or (least) upper bound [supremum] sup (f,g) such that

sup(f, g) \im f

sup(f, g) \im f

h\im f and h\im g imply h\im sup(f, g);

Instead of the definition 5.3, the following axioms characterise a lattice alternatively ([], page 18). [Lattice, version II] A lattice is an algebraic structure \L = (\L , \sqcap , \sqcup ) with two operations ``\sqcap'' and ``\sqcup'' satisfying

Remarks:

(i) With the identifications

(ii) A lattice is finite if the number of elements is finite.

(iii) The upper or lower bound of a lattice satisfy

(iv) Two lattices \L ₁ and \L₂ are isomorphic if there exists a one-to-one map I:\L ₁® \L ₂ of the lattice \L ₁ into the lattice \L ₂ such that the (binary) relations \sqcap and \sqcup are preserved; i.e., I(f\sqcap_{\L 1}g)=I(f)\sqcap_{\L 2}I(g) and I(f\sqcup_{\L 1}g)=I(f)\sqcup _{\L 2}I(g) for all f,g Î \L ₁ (see also definion 5.1).

[Orthoganal complement, orthocomplement] f¢ is a orthogonal complement, or orthocomplement of f if

(i)

(f¢)¢=f,

(ii)

f¢\sqcap f = 0,

(iii)

f¢\sqcup f = 1,

(iv)

a\fo bÞ a¢\im b¢.

[Orthocomplemented lattice] A lattice is called orthocomplete, if for all f Î \L there exists a f¢ Î \L . I.e., an orthocomplemented lattice also contains the complements.

[Subalgebra] A subalgebra of an orthocomplemented lattice \L is a subset which is closed under the operations ¢,\sqcup ,\sqcap and which contains 0 and 1. Usually a distinction is made between a subalgebra and a sublattice of a lattice. The latter one is required to be closed under the operations \sqcup ,\sqcap and not necessarily under the orthocomplement ¢.

[Finite lattice] A lattice \L is called finite if its cardinal number |\L| < ¥ is finite; i.e., if it contains only a finite number of elements.

[Exchange axiom] A lattice \L satisfies the exchange axiom if for all a,b Î \L, if a covers a\sqcap b then a\sqcup b covers b.

[Complete lattice] A lattice \L is complete if, for every subset \L ¢ Ì \L, there exists a ``meet'' \sqcap \L¢ and a ``join'' \sqcup \L ¢ in \L.

Remark:

By induction it can be shown that any finite lattice is complete.

5.3.1  Distributive lattice

The set operations of union & intersection ``È'' and ``Ç'' satisfy the distribution laws. I.e., let A,B and C be three subsets of a set, let ``\sqcap = Ç'' and ``\sqcup = È,'' then the two distributive laws AÇ(BÈC)=(AÇB)È(AÇC) and AÈ(BÇC)=(AÈB)Ç(AÈC) are always satisfied, one implying the other. General lattice structures do not necessarily satisfy the distributive laws (for example, see Fig. on p. ).

[Distributive lattice] A lattice is called distributive, if

Remarks:

(i) Every linearly ordered set is a distributive lattice.

(ii) In a distributive lattice the orthogonal complement of an element is uniquely defined.

(iii) A criterion whether or not lattices satisfy the distribution laws is

5.3.2  Boolean lattice

Example:

The set of subsets of a set is a Boolean lattice with the identifications summarised in table 5.1.

Remark:

If f\sqcap g=0, then one may write f ^g; in words ``f is orthogonal to g.''

5.3.3  Modular lattice

The following theorem is stated without proof (see, for instance, G. Birkhoff, ref. [], p. 66): Any non-modular lattice contains the lattice of Fig. 5.2 as a subalgebra.

5.3.4  Orthomodular lattice

The following implications are valid:

5.3.5  Commutator and Centre of orthomodular lattice

[Commutator]  
Two elements a and b of an orthomodular lattice \L are commuting, denoted by aCb, iff a=(a\sqcap b)\sqcup (a\sqcap b¢), or a=(a\sqcup b)\sqcap (a\sqcup b¢), or a\sqcap(a¢\sqcup b) = a\sqcap b. Let

[Centre] The centre \L^c of an orthomodular lattice \L is the set of all elements commuting with all elements of \L.

[Irreducibility] An orthomodular lattice is irreducible if \L^c = { 0,1}.

Examples:

(i) The centre of every Boolean lattice is the original Boolean lattice; i.e., if A is a Boolean lattice, A^c=A.

(ii) Every Hilbert lattice is irreducible; i.e., \SS^c = { 0,1}. For details, see, for instance, G. Kalmbach, Orthomodular Lattices [], chapters 1& 4, or Measures and Hilbert Lattices [], chapter 1.

5.3.6  Prime ideal, state

(i)

if a Î Á and b\fo a, then b Î Á,

(ii)

if a,b Î Á and a ^b (i.e., a\sqcap b=0), then a \sqcup b Î Á.

[Prime ideal] A prime ideal of an orthomodular poset L is an ideal P, P ¹ L such that a ^b implies a Î P or b Î P.

[Prime] An orthomodular poset L is called prime if, for all a,b Î L, a ¹ b, there exists a prime ideal P of L such that a Î P, b Ï P or a Ï P, b Î P.

Remarks:

(i) Let P be a prime ideal. Then x Î P or x¢ Î P;

(ii) Let P be a prime ideal. aCb and a \sqcap b Î P implies a Î P or b Î P.

[State] A two-valued state on an orthomodular poset L is a mapping s:L®{0,1} such that

(i)

s(1) = 1;

(ii)

if a ^b and a,b Î L, then s(a \sqcup b) = s(a)+ s(b).

Remark:

Let L be an orthomodular poset. Then the mapping j:S(L)® P(L), j(s) = {x Î L | s(x) = 0} is bijective [].

5.3.7  Block pasting of orthomodular lattices

Informally speaking, the term ``maximal'' refers to the greatest possible number of atoms. The construction of orthomodular lattices from a union of Boolean algebras is the ``inverse'' problem to the task of finding the block decomposition (i.e., finding the maximal Boolean subalgebras) of a given orthomodular lattice.

[Pasting, { 0,1}-pasting] 
Let { \L_i} be a collection of orthomodular (Boolean) lattices such that, for all \L_i ¹ \L_j, the following conditions are satisfied:

(i)

\L_i Ë \L_j,

(ii)

\L_i Ç\L_j is a orthomodular (Boolean) sublattice, and the partial orderings and orthocomplementations of \L_i and \L_j coincide on \L_iÇ\L_j.

In particular, if \L_i Ì \L_j={0,1} for i ¹ j, then \L = È_i \L_i is called the { 0,1}-pasting of the \L_i's as the horizontal sum.

Every orthomodular lattice is a pasting of its blocks. For a detailed discussion, see G. Kalmbach, Orthomodular Lattices [], chapter 4, in particular remark 12, p. 50, as well as M. Navara and V. Rogalewicz [].

Every Hilbert lattice (for a definition, see 5.4.6, p. pageref) is an irreducible pasting of (not necessarily disjoint) blocks. While the intersection of all blocks of a Hilbert lattice contains only the two elements 0 and 1, the intersection of two arbitrary blocks of a Hilbert lattice may contain several atoms which are common to these blocks. The pasting of its blocks forming the structure of an arbitrary Hilbert lattice is schematically drawn in Fig. 5.4.

The inverse question of whether any pasting of Boolean algebras results in an orthomodular or Hilbert lattice has been investigated by R. J. Greechie and M. Dichtl, among others. In what follows we shall introduce notations and techniques which can be used to construct orthomodular lattices from Boolean algebras. No attempt is made here to extensively review these efforts. We shall deal only with the most simple cases, i.e., with almost disjoint systems of blocks. More general pasting techniques are reviewed in G. Kalmbach, Orthomodular Lattices [], chapter 4.

[Almost disjoint system of Boolean subalgebras] 
Let B be a system of Boolean algebras. B is almost disjoint if for any pair A,B Î B at least one of the following conditions is satisfied:

(i)

A=B;

(ii)

AÇB={ 0,1};

(iii)

AÇB={ 0,1, a, a¢}, where a is an atom in A and B; and A and B share the same elements 0 and 1.

[Loop of order n] 
A finite sequence B₀,¼,B_n-1 of a system of blocks B is a loop of order n (n ³ 3) if (equality is understood as modulo n):

(i)

B_iÇB_i+1={0,1,a,a¢};

(ii)

if j Ï {i-1,i,i+1}, then B_iÇB_j={0,1};

(iii)

for distinct indices i,j,k, B_iÇB_jÇB_k={0,1}.

[Loop lemma (R. J. Greechie)] 
Let B={B_i} be an almost disjoint system of Boolean algebras. \L = È_{Bi Î B} B_i is an orthomodular partially ordered set iff B does not contain a loop of order 3. \L = È_{Bi Î B} B_i is an orthomodular lattice iff B does not contain a loop of order 3 or 4.

[Greechie lattice] 
An orthomodular lattice is a Greechie lattice if the following conditions are satisfied:

(i)

Every element can be written as a supremum of at least a countable number of mutually orthogonal atoms;

(ii)

the collection of all blocks forms an almost disjoint subset.

A Greechie diagram consists of points `` ° '', representing the atoms. Lines linking the points (atoms) belong to the same block. Two lines are crossing in a common atom. For more general results on block pasting, see chapter 4 in G. Kalmbach's monography Orthomodular Lattices [].

Examples & remarks:

(i) Greechie diagram and Hasse diagram of 2²:


Picture Omitted
                        Figure

(ii) Greechie diagram and Hasse diagram of 2³:


Picture Omitted
                        Figure

(iii) The following lattice characterised by its Greechie and Hasse diagrams is obtained by the pasting of two 2³ with one common atom.


Picture Omitted
                        Figure

(iv) This Greechie lattice is an example of an orthomodular lattice which is not modular. It is a pasting of 2² and 2³ and contains the lattice drawn in Fig. 5.2, p. pageref.


Picture Omitted
                        Figure

(v) Greechie diagram and Hasse diagram of an almost disjoint system of blocks of 2³ with a loop of the order of 3. According to the loop lemma the resulting ``pasted'' structure is no orthomodular lattice (this can also be seen by direct inspection).


Picture Omitted
                        Figure

(vi) Two-dimensional case: The {0,1}-pasting (horizontal sum) of À₁-many copies of 2² (À₁ is the cardinality of the continuum) yields the Hilbert space C(\"₂ ), where the dimension (i.e., the maximal number of linear independent vectors of \") is two.

5.4  Examples

5.4.1  Set of subsets of a set

5.4.2  Partition logic

Partition logics are introduced here to identify the experimental logics of generic (finite) automata, in particular of automata of the Mealy type.

Example:

Let M={1,2,3,4,5,6} and P={P₁,P₂} with P₁={{1,4,5},{2},{3,6}} and P₂={{1,2,4},{5},{3,6}}. The Greechie and Hasse diagrams of this logic are shown in Fig. , p. . For much more examples, see chapter .

5.4.3  Greatest common divisor and least common multiplier

5.4.4  Lattices defined by Hasse diagrams

Lattices defined by 5.5(d) and 5.5(e) are not distributive, since for 5.5(d),

5.4.5  Lattice of classical propositional calculus

The identification of relations in lattice theory with relations in the propositional calculus is represented in table 5.3.

Remarks:

(i) The implication relation p₁® p₂ can be composed from the other relations Ù,Ú, Ø (and vice versa) by (Øp₁ Úp₂), or by

(ii) p₁ = p₂ can be composed as (p₁Ùp₂)Ú(Øp₁ ÙØp₂).

(iii) The lattice defined by the propositional calculus is distributive, i.e., the following pairs of formulas (separated by ``='') are equivalent:

(iv) The lattice is orthocomplemented; i.e.,

(v) By (iii) & (iv), the classical propositional calculus is Boolean.

5.4.6  Lattice of subspaces of a Hilbert space - Hilbert lattices

Definition of Hilbert space

[Field] A set of scalars K or (K,+,·) is a field if

(I)

to every pair a,b of scalars there corresponds a scalar a+b in such a way that

(i)

a+b=b+a (commutativity);

(ii)

a+(b+c)=(a+b)+c (associativity);

(iii)

there exists a unique zero element 0 such that a+0=a for all a Î K;

(iv)

To every scalar a there corresponds a unique scalar -a such that a+(-a)=0.

(II)

to every pair a,b of scalars there corresponds a scalar ab, called product in such a way that

(i)

ab=ba (commutativity);

(ii)

a(bc)=(ab)c (associativity);

(iii)

there exists a unique non-zero element 1, called one, such that a1=a for all a Î K;

(iv)

To every non-zero scalar a there corresponds a unique scalar a^-1 such that aa^-1=1.

(III)

a(b+c)=ab +ac (distributivity).

Examples: The sets \Q , \R , \C of rational, real and complex numbers with the ordinary sum and scalar product operators ``+, ·'' are fields.

[Linear space] Let M be a set of objects such as vectors, functions, series et cetera. A set M is a linear space if

(I)

there exists the operation of (generalised) ``addition,'' denoted by ``+'' obeying

(i)

f+g Î M for all f,g Î M (closedness under ``addition'');

(ii)

f+g=g+f (commutativity);

(iii)

f+(g+h)=(f+g)+h=f+g+h (associativity);

(iv)

there exists a neutral element 0 for which f+0=f for all f Î M;

(v)

for all f Î M there exists an inverse -f, defined by f+(-f)=0;

(II)

there exists the operation of (generalised) ``scalar multiplication'' with elements of the field (K,+,·) obeying

(vi)

a Î K and f Î M then af Î M (closedness under ``scalar multiplication'');

(vii)

a(f+g)=af+ag and (a+b)f=af+bf (distributive laws);

(viii)

a(bf)=(ab)f=abf (associativity);

(ix)

There exists a ``scalar unit element'' 1 Î K for which 1f=f for all f Î M.

Examples:

(i) vector spaces M=\Rⁿ with K=\R or \C;

(ii) M=l₂, K=\C, the space of all infinite sequences

(iii) the space of continuous functions, complex-valued (real-valued) functions M=C(a,b) over an open or closed interval (a,b) or [a,b] with K=\C (K=\R);

[Metric, norm, inner product] 
A metric, denoted by , is a binary function which associates a distance of two elements of a linear vector space and which satisfies the following properties:

(i)

(f,g) Î \R for all f,g Î M;

(ii)

(f,g) = (g,f) for all f,g Î M;

(iii)

(f,g)=0 Û f=g;

(iv)

(f,g) £ (f,h)+(g,h) for all h Î M and every pair f,g Î M.

(i)

\n f \n ³ 0 for all f Î M;

(ii)

\n f\n = 0Û f=0;

(iii)

\n f+g\n £ \n f\n +\n g \n ;

(iv)

\n af\n = |a | \n f\n for all a Î K and f Î M (homogeneity).

(i)

\l f | g\r = \l g | f\r^* for all f,g Î M;

(ii)

\l f | ag\r = a \l f | g\r for all f,g Î M and a Î K;

(iii)

\l f | g₁ +g₂\r = \l f | g₁ \r + \l f | g₂ \r for all f,g₁,g₂ Î M;

(iv)

\l f | f \r ³ 0 for all f Î M;

(v)

\l f | f \r = 0 Û f=0.

Remarks:

(i) With the identifications

(ii) The Schwarz inequality

[Separability, completeness] 
A linear space M is separable if there exists a sequence {f_n | n Î \N , f_n Î M} such that for any f Î M and any e > 0, there exists at least one element f_i of this sequence such that

[Hilbert space, Banach space] 
A Hilbert space \" is a linear space, equipped with an inner product, which is separable & complete.
A Banach space is a linear space, equipped with a norm, which is separable & complete.

Example:

l₂,\C [see linear space example (ii)] with \l f | g\r = å_i x_i^* y_i.

[Subspace, orthogonal subspace] 
A subspace § Ì \" of a Hilbert space is a subset of \" which is closed under scalar multiplication and addition, i.e., f,g Î H, a Î KÞ af Î §,  f+g Î §, and which is separable and complete.

An orthogonal subspace § ^{^} of § is the set of all elements in the Hilbert space \" which are orthogonal to elements of § , i.e.,

Remarks:

(i) (§ ^{^})^{^} = § ^{^^} = § ;

(ii) every orthogonal subspace is a subspace;

(iii) A Hilbert space can be represented as a direct sum of orthogonal subspaces.

[Linear functional] A map F:\"® K is a linear functional on \" if

(i)

F(f+g)=F(f)+F(g),

(ii)

F(af)=aF(f) with f,g Î \", a Î K.

[Dual Hilbert space] There exists a one-to-one map between the elements f of a Hilbert space \" and the elements of F of the set \"^f of bounded linear functionals on \", such that

(i)

F_f+F_g=F_f+g,

(ii)

aF_f=F_{a^* f},

(iii)

áF_f | F_gñ^f = ág | fñ

Remarks:

(i) \"={ f,g,h, ¼} and \"^f = { F_f,F_g,F_h, ¼} are isomorphic; instead of h º F_h, one could write h_F º F;

(ii) (\"^f )^f = \".

[Isomorphism of Hilbert spaces] All separable Hilbert spaces of equal dimension with the same field K are isomorphic.

Compatibility

[Compatibility] Two subspaces § ₁ and § ₂ of a Hilbert space are called compatible, denoted by §₁ « § ₂, if

Remarks:

(i) §₁ « § ₂ Û § ₁ \sqcup (§ ₂ \sqcap § ₁^{^} )=§ ₁ \sqcup § ₂ = § ₂ \sqcup (§ ₁ \sqcap § ₂^{^} ).

(ii) The relation « is symmetric, i.e., §₁ « § ₂ Û §₂ « § ₁ .

Definition of Hilbert lattices

[Hilbert lattice]  
A Hilbert lattice is the lattice of all closed subspaces of a Hilbert space \"; it is denoted by \SS . The ``meet'' \sqcap   is identified with the closure of the linear span, the ``join'' \sqcup    is identified with the set theoretic union and the ``complement'' of a subspace with its orthogonal subspace. The identification of relations and operations in lattice theory with relations and operations in Hilbert space is represented in table .

Remarks:

(i) \SS is an orthocomplemented lattice.

(ii) In general, § is not distributive. Let for instance § ¢,§ ,§ ^{^} be subsets of a Hilbert space \" with § ¢ ¹ §,   § ¢ ¹ § ^{^} , then (see Fig. , drawn from J. M. Jauch [], p. 27)

(iii) A finite dimensional Hilbert lattice is modular.

(iv) Since Hilbert lattices are orthomodular lattices, they can be constructed by the pasting of blocks (blocks are maximal Boolean subalgebras); the blocks need not be (almost) disjoint. This fact will be used for the construction of automata yielding arbitrary finite subalgebras of Hilbert lattices as propositional calculi. See chapter , p. for details.

(v) In Hilbert lattices, the orthoarguesian law is satisfied. For a definition and details, see J. R. Greechie [], G. Kalmbach [] and R. Giuntini [], p. 138. The orthoarguesian law is not satisfied by general orthomodular lattices. I.e.,

Algebraic characterisation of Hilbert lattices

An infinite dimensional \SS is a complete, atomic, irreducible, orthomodular lattice satisfying the exchange axiom (i.e., if a covers a\sqcap b then a\sqcup b covers b). In some notations these criteria are the defining features of Hilbert lattices (e.g., G. Kalmbach, Measures and Hilbert Lattices [], p. 11). Yet, they are also satisfied by lattices of Keller spaces [,,]; Keller spaces are different from Hilbert spaces in important aspects.

A complete axiomatisation for lattices of separable complex Hilbert spaces has been given by W. J. Wilbur []; see also the review by R. Piziak []: [(W. J. Wilbur [])] A lattice \L is isomorphic to a complex Hilbert lattice iff it satisfies the following conditions (i)-(vii).

(i)

\L has at least one point;

(ii)

the length ||\L || = À₀ (for a definition of length, see 5.2, p. pageref);

(iii)

If a and a^{^} are nonzero elements of \L and x Î \L, then there exist points y,z Î \L with y < a, z < a^{^} and x < y\sqcup z;

(iv)

If a,b,c Î \L and if a\sqcup b is less than the sum of a finite set of points in \L, and if c < a, then a\sqcap (b\sqcup c)=(a\sqcap b)\sqcupc;

(v)

If x,y Î \L and x ¹ y, then there is is a distinct third point x ¹ z ¹ y, z Î \L with z < x\sqcup y.

(vi)

Given any four distinct points u,v,w,x Î \L with u \sqcup v=w\sqcup x, then there exist points y,z Î \L with y\not < (v\sqcup z), y\not < (w\sqcup x), z\not < (w\sqcup x), z\not < (u\sqcup y), such that ||w\sqcup x\sqcup y\sqcup z|| = 2 and (u\sqcup y)\sqcap (z\sqcup x) < [(v\sqcup z)\sqcap (w\sqcup y)]\sqcup[(u\sqcup v)\sqcap (z\sqcup y)];

(vii)

(Pappus' theorem) If u,v,w,x,y,z Î \L are six distinct points with ||u\sqcup v\sqcup w\sqcup x\sqcup y\sqcup z|| = 2 and if (u\sqcup v)\sqcap (w\sqcup z)\sqcap (y\sqcup z) ¹ 0 and if (x\sqcup y)\sqcap (z\sqcup u)\sqcap (v\sqcup w) ¹ 0, then (u\sqcup x)\sqcap (v\sqcup y)\sqcap (w\sqcup z) ¹ 0.

However, as already conceded by W. J. Wilbur, the above characterisation, in particular axiom (ii) and countable completeness, is not purely algebraic. One may ask if it is possible to develop an axiomatisation of Hilbert lattices in purely algebraic terms. An answer to this question is unknown. For related discussions, see, for instance, G. Takeuti [] and G. Kalmbach [,]. It might be conjectured that there is no recursive enumeration of the axioms of Hilbert lattices [].

5.4.7  The algebra of projections

[Projection] A projection is an operator E defined on a Hilbert space \" which is self-adjoint and idempotent, i.e.,

There is an isomorphism between the set of projections, denoted by \PP and all closed subspaces \SS of \": given a projection E, the corresponding subspace is § = E(\"); given a closed subspace §, any f Î \" can be decomposed uniquely as a sum f=g+h, where g Î § and h Î §^{^}; the projection corresponding to § is then the operator E determined by Ef=g. This one-to-one correspondence allows a translation of the lattice structure of the subsets of Hilbert space discussed before into the algebra of projections. §₁ « §₂ Û E₁ E₂ = E₂ E₁ , where E_i is the projection onto §_i, i=1,2. (This is a reason why quantum logic is also said to correspond to a non-commutative probability theory.)

The identification of relations and operations in lattice theory with the relations and operations in the lattice of projections is represented in table ([], p. 37).

5.4.8  Lattice of quantum propositional calculus

In what follows the mathematical formalism of quantum mechanics is very briefly reviewed. No attempt is being made to give a complete set of axioms. See also, for instance, J. von Neumann [], A. Messiah [], L. E. Ballentine []. Its primitive concepts are those of state and observable. An observable is represented by a self-adjoint operator O on a Hilbert space \". In the spectral representation, O can be written as

The projections E_n correspond to the physical properties of a quantum system. In J. von Neumann's words ([], p. 249; in our notation, E is a proposition):

Apart from the physical quantities Â, there exists another category of concepts that are important objects of physics - namely the properties of the states of the system S. Some such properties are: that a certain quantity  takes the value l - or that the value of  is positive - ¼

To each property E we can assign a quantity which we define as follows: each measurement which distinguishes between the presence or absence of E is considered as a measurement of this quantity, such that its value is 1 if E is verified, and zero in the opposite case. This quantity which corresponds to E will also be denoted by E.

Such quantities take only the values of 0 and 1, and conversely, each quantity  which is capable of these two values only, corresponds to a property E which is evidently this: ``the value of  is ¹ 0.'' The quantities E that correspond to the properties are therefore characterized by this behavior.

That E takes on only the values 0,1 can also be formulated as follows: Substituting E into the polynomial F(l)=l-l² makes it vanish identically. If E has the operator E, then F(E) has the operator F(E)=E-E², i.e., the condition is that E-E²=0 or E=E². In other words: the operator E of E is a projection.

The projections E therefore correspond to the properties E (through the agency of the corresponding quantities E which we just defined). If we introduce, along with the projections E, the closed linear manifold M, belonging to them (E=P _M), then the closed linear manifolds correspond equally to the properties of E.

In the case of nondegenerate eigenvalues r_n and eigenvectors |nñ, O can be written as

G. Birkhoff and J. von Neumann suggested [], that, roughly speaking, the ``logic of quantum events'' - or, by another wording, quantum logic or the quantum propositional calculus - should be obtainable from the formal representation of physical properties. They conjectured that the Hilbert space formalism of quantum mechanics [] is an appropriate theory of quantum events. Since, in this formalism, projection operators correspond to the physical properties of a quantum system, quantum logics is modelled in order to be isomorphic to the lattice of projections \PP of the Hilbert space \", which in turn is isomorphic to the lattice \SS of the set of subspaces of a Hilbert space. I.e., by assuming the physical validity of the quantum Hilbert space formalism, the corresponding isomorphic logical structure is investigated. Since, in this approach, quantum theory comes first and the logical structure of the phenomena are derived by analysing the theory, this could be considered a ``top-down'' method. In the case of the automata propositional calculus (see below, chapter , p. ) one proceeds ``bottom-up'', i.e., by analysing the structure of elementary processes first and conjecturing a corresponding linear space structure afterwards.