The recognition of the physical aspect of the ChurchTuring thesisthe postulated equivalence between the informal notion of ``mechanical computation'' (algorithm) and recursive function theory as its formalized counterpartis 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 ChurchTuring 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 ChurchTuring thesis, often referred to as ``CookKarp 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 (onetoone) 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. 2427] 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 outputequivalent to the tossing of a fair coinsuch 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 subsegments of length 1/2, 1/4, 1/8, ¼, as of `choppedoff' 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 yesorno 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ópezEscobar [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 DOloop; 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 informationdeletion or other manytoone operationshas raised considerable attention in the physics community [38]. Figure 1 [36] depicts a flow diagram, illustrating the difference between onetoone, manytoone and onetomany computation.
Classical reversible computation [29,2,19,3,36] is characterized by a singlevalued invertible (i.e., bijective or onetoone) 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 singlevalued inverse, such as and or or; i.e., the input cannot be deduced from the output. Also deletion of information or other many (states)toone (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 onetomany 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 onetomany operations, in particular copying, and to accept merely onetoone 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 onetoone. 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}=U^{f} (where f represents the adjoint operator); i.e., UU^{f} = 1. As a consequence, the nocloning theorem [23,61,40,41,20,11] states that certain onetomany 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
onetoone 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 onetoone 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×nmatrix. Let Y_{i} be the i'th element in the vectorial representation of some (s,i), and let U_{ij} 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, P_{1}={1}.
For n=2, P_{2}={(

 



 



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 
s_{1}  s_{2}  s_{1}  1  2 
s_{2}  s_{2}  s_{1}  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, (s_{1},1)®(s_{2},1)®(s_{2},2)®(s_{1},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 onetoone 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'' regionthe 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 onetoone (bijectively, homomorphically) inside the black box, but this information is handled onetoone 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 onetoone evolution also for the environment at and outside of the black box. That is, one deals with a homogeneous and uniform onetoone evolution ``inside'' and ``outside'' of the black box, thereby assuming that the experimenter also evolves onetoone 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 onetoone 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 onetoone 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 
s_{1}  s_{1}  s_{3}  2  2 
s_{2}  s_{2}  s_{1}  1  1 
s_{3}  s_{3}  s_{2}  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 complexityany measurement can be ``undone'' by a proper reconstruction of the wavefunction. 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 comeasurable 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 onetoone 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 onetoone 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].