The recognition of the physical aspect of the Church-Turing thesis-the postulated equivalence between the informal notion of ``mechanical computation'' (algorithm) and recursive function theory as its formalized counterpart-is not new [18,7,8,38,45,43]. In particular Landauer points out that computers are physical systems, that computations are physical processes and therefore are subject to the laws of physics [29,30,31,28,32,33,34,36,35]. As Deutsch puts it [15,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 noncomputable functions. We might still know of them and invoke them in mathematical proofs (which would presumably be called `nonconstructive') but we could not perform them.''See also Pitowsky's review [44]. One may indeed perceive a strong interrelationship between the way we do mathematics, formal logic, the computer sciences and physics. All these sciences have been developed and constructed by us in the context of our (everyday) experiences.
The Computer Sciences are well aware of this connection. See, for instance, Odifreddi's review [43], the articles by Rosen [46] and Kreisel [27], or Davis' book [14,p. 11], where the following question is asked:
`` ¼ 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 noncomputable function?''
Thus, it comes as no surprise that the Church-Turing thesis is under permanent attack from the physical sciences. For just two such attempts in the recent literature, we refer to the articles by Siegelmann [52] and Hogarth [24,25].
Even more so, this applies to the weak Church-Turing thesis, often referred to as ``Cook-Karp thesis,'' putting into question the robustness of the notion of tractability or polynomial time complexity class with respect to variations of ``reasonable'' models of computation. One particular famous contemporary case is quantum computing. There, it has been shown that at least factoring may require polynomial time on quantum computers within ``reasonable statistics'' [51,17].
We shall take out two examples of connections between physics and computation. First, we briefly review reformulations of Zeno's argument of Achilles and the Tortoise (Hector). This paradox purportedly seems to have been originally directed against motion [37,26,21]. In this context it can be applied against the uncritical use of continua and dense sets in general. Later on, we shall investigate reversible computations, more specifically computations corresponding to bijective (one-to-one) maps and its possible connections with measurement operations.
In what follows, an oracle problem solver will be introduced whose capacity exceeds and outperforms any presently realisable, finite machine and also any universal computer such as the Turing machine. We follow previous discussions (cf. [53,pp. 24-27] and [54,57,56,55]).
Its design is based upon a universal computer with ``squeezed'' cycle times of computation according to a geometric progression. The only difference between universal computation and this type of oracle computation is the speed of execution. But what a difference indeed: Zeno squeezed oracle computation performs computations in the limit of infinite time of computation. In order to achieve this limit, two time scales are introduced: the intrinsic time scale of the process of computation, which approaches infinity in finite extrinsic or proper time of some outside observer.
As a consequence, certain tasks which lie beyond the domain of recursive function theory become computable and even tractable. For example, the halting problem and any problem codable into a halting problem would become solvable. It would also be possible to produce an otherwise uncomputable and random output-equivalent to the tossing of a fair coin-such as Chaitin's W [12,9] in finite proper time. We shall come back to these issues, in particular consistency, shortly.
A very similar setup has been introduced by Hermann Weyl [59], which was discussed by Grünbaum [22,p. 630]. Already Weyl raised the question whether it is kinematically feasible for a machine to carry out an infinite sequence of operations in finite time. Weyl writes [59,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!
See also the articles by Thomson [58], Benacerraf [1], Rucker [47], Pitowsky [44], Earman and Norton [16] and Hogarth [24,25], as well as E. W. Beth, [5,p. 492] and K. López-Escobar [39].
Let us come back to the original goal: the construction of a ``Zeno squeezed oracle,'' or, in Grünbaum's terminology, of an ``infinity machine.'' As sketched before, it can be conceived by considering two time scales t and t which are related as follows.
|
There is no commonly accepted principle which would forbid such an oracle a priori. In particular, classical mechanics postulates space and time continua as a foundational principle. One might argue that such an oracle would require a geometric energy increase resulting in an infinite consumption of energy. Yet, no currently accepted physical principle excludes us from assuming that every geometric decrease in cycle time could be associated with a geometric progression in energy consumption, at least up to some limiting (e.g., Planck) scale.
Nevertheless, it can be shown by a diagonalization argument that the application of such oracle subroutines would result in a paradox. The paradox is constructed in the context of the halting problem. It is formed in a similar manner as Cantor's diagonalization argument. Consider an arbitrary algorithm B(x) whose input is a string of symbols x. Assume that there exists (wrong) an ``effective halting algorithm'' HALT, implementable on the oracle described above, which is able to decide whether B terminates on x or not.
Using HALT(B(x)) we shall construct another deterministic computing agent A, which has as input any effective program B and which proceeds as follows: Upon reading the program B as input, A makes a copy of it. This can be readily achieved, since the program B is presented to A in some encoded form # (B), i.e., as a string of symbols. In the next step, the agent uses the code # (B) as input string for B itself; i.e., A forms B(#(B)), henceforth denoted by B(B). The agent now hands B(B) over to its subroutine HALT. Then, A proceeds as follows: if HALT(B(B)) decides that B(B) halts, then the agent A does not halt; this can for instance be realized by an infinite DO-loop; if HALT(B(B)) decides that B(B) does not halt, then A halts.
We shall now confront the agent A with a paradoxical task by choosing A's own code as input for itself.-Notice that B is arbitrary and has not yet been specified and we are totally justified to do that: The deterministic agent A is representable by an algorithm with code # (A). Therefore, we are free to substitute A for B.
Assume that classically A is restricted to classical bits of information. Then, whenever A(A) halts, HALT(A(A)) forces A(A) not to halt. Conversely, whenever A(A) does not halt, then HALT(A(A)) steers A(A) into the halting mode. In both cases one arrives at a complete contradiction.
Therefore, at least in this example, too powerful physical models (of computation) are inconsistent. It almost goes without saying that the concept of infinity machines is neither constructive nor operational in the current physical framework.
Quantum mechanics offers a rescue;
yet in a form which is not common in ``classical'' recursion theory.
The paradox is resolved when
A is allowed a nonclassical qubit of information.
Classical information theory is based on the
classical bit as
fundamental atom.
Any classical bit is in one of two
classical states t (often interpreted as ``true'') and f (often
interpreted as ``false'').
In quantum information theory
the most elementary unit of information is
the quantum bit,
henceforth called qubit.
Qubits can be physically represented by a coherent
superposition
of two orthonormal quantum
states t and f.
The quantum bit states
|
Assume now that
|0ñ = |1,0ñ
and |1ñ = |0,1ñ
correspond to the halting and to the nonhalting
states, respectively.
A's task can consistently be performed
if it inputs a qubit corresponding to the fixed point state
of the diagonalization (not) operator
|
| (3) |
| (4) |
| (5) |
The connection between information and physical entropy, in particular the entropy increase during computational steps corresponding to an irreversible loss of information-deletion or other many-to-one operations-has raised considerable attention in the physics community [38]. Figure 1 [36] depicts a flow diagram, illustrating the difference between one-to-one, many-to-one and one-to-many computation.
Classical reversible computation [29,2,19,3,36] is characterized by a single-valued invertible (i.e., bijective or one-to-one) evolution function. In such cases it is always possible to ``reverse the gear'' of the evolution, and compute the input from the output, the initial state from the final state.
In irreversible computations, logical functions are performed which do not have a single-valued inverse, such as and or or; i.e., the input cannot be deduced from the output. Also deletion of information or other many (states)-to-one (state) operations are irreversible. This logical irreversibility is associated with physical irreversibility and requires a minimal heat generation of the computing machine and thus an entropy increase.
It is possible to embed any irreversible computation in an appropriate environment which makes it reversible. For instance, the computer could keep the inputs of previous calculations in successive order. It could save all the information it would otherwise throw away. Or, it could leave markers behind to identify its trail, the Hänsel and Gretel strategy described by Landauer [36]. That, of course, might amount to huge overheads in dynamical memory space (and time) and would merely postpone the problem of throwing away unwanted information. But, as has been pointed out by Bennett [2], for classical computations, in which copying and one-to-many operations are still allowed, this overhead could be circumvented by erasing all intermediate results, leaving behind only copies of the output and the original input. Bennett's trick is to perform a computation, copy the resulting output and then, with one output as input, run the computation backward. In order not to consume exceedingly large intermediate storage resources, this strategy could be applied after every single step. Notice that copying can be done reversible in classical physics if the memory used for the copy is initially considered to be blank.
Quantum mechanics, in particular quantum computing, teaches us to restrict ourselves even more and exclude any one-to-many operations, in particular copying, and to accept merely one-to-one computational operations corresponding to bijective mappings [cf. Figure 1a)]. This is due to the fact that the unitary evolution of the quantum mechanical state state (between two subsequent measurements) is strictly one-to-one. Per definition, the inverse of a unitary operator U representing a quantum mechanical time evolution always exists. It is again a unitary operator U-1=Uf (where f represents the adjoint operator); i.e., UUf = 1. As a consequence, the no-cloning theorem [23,61,40,41,20,11] states that certain one-to-many operations are not allowed, in particular the copying of general (nonclassical) quantum bits of information.
In what follows we shall consider a particular example of a
one-to-one deterministic computation. Although tentative in its present
form, this example may illustrate the conceptual strength of reversible
computation. Our starting point are
finite automata [42,13,6,48,10],
but of a very particular,
hitherto unknown sort. They are characterized by a finite set S of
states, a finite input and output alphabet I and O, respectively.
Like for Mealy automata, their temporal evolution and output functions
are given by d:S×I® S, l:S×I® O. We additionally require one-to-one reversibility,
which we interpret in this context as follows. Let I=O, and let the
combined (state and output) temporal evolution be associated with a
bijective map
| (6) |
The elements of the Cartesian product S×I can be arranged as a linear list of length n corresponding to a vector. In this sense, U corresponds to a n×n-matrix. Let Yi be the i'th element in the vectorial representation of some (s,i), and let Uij be the element of U in the i'th row and the j'th column. Due to determinism, uniqueness and invertibility,
Let us be more specific.
For n=1, P1={1}.
For n=2, P2={(
|
| ||
|
|
|
| ||
|
|
|
The correspondence between permutation matrices and
reversible automata is straightforward. Per definition [cf. Equation
(6)], every reversible automaton is representable by some
permutation matrix. That every n×n permutation matrix
corresponds to an automaton can be demonstrated by
considering the simplest
case of a one state automaton with n input/output symbols.
There exist less trivial identifications. For example,
let
|
| d | l | |||
| S\I | 1 | 2 | 1 | 2 |
| s1 | s2 | s1 | 1 | 2 |
| s2 | s2 | s1 | 2 | 1 |
The associated flow diagram is drawn in Figure 2.
Since U has a cycle 3; i.e., (U)3=1, irrespective of the initial state, the automaton is back at its initial state after three evolution steps. For example, (s1,1)®(s2,1)®(s2,2)®(s1,1).
The discrete temporal evolution (6) can, in matrix
notation, be represented by
| (7) |
Let us come back to our original issue of modelling the measurement process within a system whose states evolve according to a one-to-one evolution. Let us artificially divide such a system into an ``inside'' and an ``outside'' region. This can be suitably represented by introducing a black box which contains the ``inside'' region-the subsystem to be measured, whereas the remaining ``outside'' region is interpreted as the measurement apparatus. An input and an output interface mediate all interactions of the ``inside'' with the ``outside,'' of the ``observed'' and the ``observer'' by symbolic exchange. Let us assume that, despite such symbolic exchanges via the interfaces (for all practical purposes), to an outside observer what happens inside the black box is a hidden, inaccessible arena. The observed system is like the ``black box'' drawn in Figure 3.
Throughout temporal evolution, not only is information transformed one-to-one (bijectively, homomorphically) inside the black box, but this information is handled one-to-one after it appeared on the black box interfaces. It might seem evident at first glance that the symbols appearing on the interfaces should be treated as classical information. That is, they could in principle be copied. The possibility to copy the experiment (input and output) enables the application of Bennett's argument: in such a case, one keeps the experimental finding by copying it, reverts the system evolution and starts with a ``fresh'' black box system in its original initial state. The result is a classical Boolean calculus.
The scenario is drastically changed, however, if we assume a one-to-one evolution also for the environment at and outside of the black box. That is, one deals with a homogeneous and uniform one-to-one evolution ``inside'' and ``outside'' of the black box, thereby assuming that the experimenter also evolves one-to-one and not classically. In our toy automaton model, this could for instance be realized by some automaton corresponding to a permutation operator U inside the black box, and another reversible automaton corresponding to another U¢ outside of it. Conventionally, U and U¢ correspond to the measured system and the measurement device, respectively.
In such a case, as there is no copying due to one-to-one evolution, in order to set back the system to its original initial state, the experimenter would have to erase all knowledge bits of information acquired so far. The experiment would have to evolve back to the initial state of the measurement device and the measured system prior to the measurement. As a result, the representation of measurement results in one-to-one reversible systems may cause a sort of complementarity due to the impossibility to measure all variants of the representation at once.
Let us give a brief example. Consider the 6×6 permutation matrix
|
| d | l | |||
| S\I | 1 | 2 | 1 | 2 |
| s1 | s1 | s3 | 2 | 2 |
| s2 | s2 | s1 | 1 | 1 |
| s3 | s3 | s2 | 1 | 2 |
The evolution is
|
Thus after the input of just one symbol, the automaton states can be
grouped into experimental equivalence classes [53]
|
In this epistemic model, the interface symbolizes the cut between the observer and the observed. The cut appears somewhat arbitrary in a computational universe which is assumed to be uniformly reversible.
What has been discussed above is very similar to the opening, closing and reopening of Schrödinger's catalogue of expectation values [49,p. 53]: At least up to a certain magnitude of complexity-any measurement can be ``undone'' by a proper reconstruction of the wave-function. A necessary condition for this to happen is that all information about the original measurement is lost. In Schrödinger's terms, the prediction catalog (the wave function) can be opened only at one particular page. We may close the prediction catalog before reading this page. Then we can open the prediction catalog at another, complementary, page again. By no way we can open the prediction catalog at one page, read and (irreversible) memorize the page, close it; then open it at another, complementary, page. (Two noncomplementary pages which correspond to two co-measurable observables can be read simultaneously.)
From this point of view, it appears that, strictly speaking, irreversibility may turn out to be an inappropriate concept both in computational universes generated by one-to-one evolution as well as for quantum measurement theory. Indeed, irreversibility may have been imposed upon the measurement process rather heuristically and artificially to express the huge practical difficulties associated with any backward evolution, with ``reversing the gear'', or with reconstructing a coherent state. To quote Landauer [33,section 2],
``What is measurement? If it is simply information transfer, that is done all the time inside the computer, and can be done with arbitrary little dissipation.''
Let us conclude with a metaphysical speculation. In a one-to-one invertible universe, any evolution, any step of computation, any single measurement act reminds us of a permanent permutation, reformulation and reiteration of one and the same ``message''-a ``message'' that was there already at the beginning of the universe, which gets transformed but is neither destroyed nor renewed. This thought might be very close to what Schrödinger had in mind when contemplating about Vedic philosophy [50].