The Church-Turing thesis as a guiding principle for physics

Karl Svozil

Abstract

Two aspects of the physical side of the Church-Turing thesis are discussed. The first issue is a variant of the Eleatic argument against motion, dealing with Zeno squeezed time cycles of computers. The second argument reviews the issue of one-to-one computation, that is, the bijective (unique and reversible) evolution of computations and its relation to the measurement process.

1  Introduction

It is reasonable to require from a ``useful'' theory of computation that any capacity and feature of physical systems (interpretable as ``computing machines'') should be reflected therein and vice versa.

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.

2  Infinity machines by Zeno squeezed time cycles

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.

The proper time t measures the physical system time by clocks in a way similar to the usual operationalisations; whereas
a discrete cycle time t=0,1,2,3, characterizes 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. Hence, for k < 1, let any time cycle of t, if measured in terms of t, be squeezed by a factor of k with respect to the foregoing time cycle i.e.,
t0
=
0,    t1=k ,    tt+1-tt = k(tt-tt-1),
(1)
tt
=
t

n=0 
kn-1=  k(kt-1)

k-1
    .
(2)
Thus, in the limit of infinite cycle time t , the proper time t = k/(1-k) remains finite.
We just mention that for the model introduced here only dense space-time would be required.

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
|a,b = a

1
0


+b

0
1


= a|0+b|1 ,
with |a|2+|b|2=1, a,b C form a continuum.

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
^
D
 
= not = t1 =

0
1
1
0


=|10|+ |01|.
That is,
^
D
 
|* = |*.
(3)
The fixed point state |* is just the eigenstate of the diagonalization operator [^D] with eigenvalue 1. Notice that the eigenstates of [^D] are
|I,|II =  1

2




1
0




0
1




=  1

2
(|0|1)
(4)
with the eigenvalues +1 and -1, respectively. Thus, the nonparadoxical, fixed point qubit in the basis of |0 and |1 is given by
|* = |  1

2
,  1

2
= |I.
(5)
In natural language, this qubit solution corresponds to the statement that it is impossible for the agent to control the outcome, since there is a fifty percent chance for each of the classical bit states |0 and |1 to be ``stimulated'' at tA. The impossibility of outcome control is indeed encountered in quantum mechanics. Stated differently: at the level of probability amplitudes, quantum theory permits a Zeno squeezed oracle. But at the level of observable probabilities, this is exactly nullified, as the result of the computation appears to occur entirely at random.

3  One-to-one computational paths and measurement

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.

0.50mm
Picture Omitted
Figure 1: In this flow diagram, the lowest ``root'' represents the initial state of the computer. Forward computation represents upwards motion through a sequence of states represented by open circles. Different symbols pi correspond to different initial computer states. a) One-to-one computation. b) Many-to-one junction which is information discarding. Several computational paths, moving upwards, merge into one. c) One-to-many computation is allowed only if no information is created and discarded; e.g., in copy-type operations on blank memory. From Landauer [36].

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
U:(s,i) (d(s,i),l(s,i)),
(6)
with s S and i I. The state and output symbol could be ``fed back'' consecutively; such that N evolution steps correspond to UN=

(UU)


N  times
 
.

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,

Uij {0,1};
orthogonality: U-1=Ut (superscript t means transposition) and (U-1)ij=Uji;
double stochasticity: the sum of each row and column is one; i.e., i=1n Uij = j=1n Uij=1.
Since U is a square matrix whose elements are either one or zero and which has exactly one nonzero entry in each row and exactly one in each column, it is a permutation matrix. Let Pn denote the set of all n×n permutation matrices. Pn forms the permutation group (sometimes referred to as the symmetric group) of degree n. (The product of two permutation matrices is a permutation matrix, the inverse is the transpose and the identity 1 belongs to Pn.) Pn has n! elements. Furthermore, the set of all doubly stochastic matrices forms a convex polyhedron with the permutation matrices as vertices [4,page 82].

Let us be more specific. For n=1, P1={1}.
For n=2, P2={(
1
0
0
1
),(
0
1
1
0
)}.
For n=3,
P3=







1
0
0
0
1
0
0
0
1




,



1
0
0
0
0
1
0
1
0




,



0
1
0
0
0
1
1
0
0




,



0
1
0
1
0
0
0
0
1




,



0
0
1
1
0
0
0
1
0




,



0
0
1
0
1
0
1
0
0








.

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
U =





0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0






.
The transition and output functions of one associated reversible automaton is listed in table 1.

d l
S\I 1212
s1s2s1 12
s2s2s1 21
Table 1: Transition and output table of a reversible automaton with two states S={s1, s2} and two input/output symbols I = {1,2}.

The associated flow diagram is drawn in Figure 2.

1.20mm
Picture Omitted
Figure 2: Flow diagram of one evolution cycle of the reversible automaton listed in Table 1.

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
UY(N) = Y(N+1)=UN+1Y(0),
(7)
where again N=0,1,2,3, is a discrete time parameter.

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.

0.9mm
Picture Omitted
Figure 3: A system in a black box with an input interface and an output interface.

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
U =









0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0










corresponding to a reversible 3-state automaton with two input/output symbols 1,2 listed in table 2.

d l
S\I 1212
s1s1s3 22
s2s2s1 11
s3s3s2 12
Table 2: Transition and output table of a reversible automaton with three states S={s1, s2, s3} and two input/output symbols I = {1,2}.

The evolution is










(s1,1)
(s1,2)
(s2,1)
(s2,2)
(s3,1)
(s3,2)










U

 










(s1,2)
(s3,2)
(s2,1)
(s1,1)
(s3,1)
(s2,2)










U

 










(s3,2)
(s2,2)
(s2,1)
(s1,2)
(s3,1)
(s1,1)










U

 










(s2,2)
(s1,1)
(s2,1)
(s3,2)
(s3,1)
(s1,2)










U

 










(s1,1)
(s1,2)
(s2,1)
(s2,2)
(s3,1)
(s3,2)










.
The associated flow diagram is drawn in Figure 4.

1.20mm
Picture Omitted
Figure 4: Flow diagram of four evolution cycles of the reversible automaton listed in Table 2.

Thus after the input of just one symbol, the automaton states can be grouped into experimental equivalence classes [53]
v(1)={{1},{2,3}},   v(2)={{1,3},{2}}.
The associated partition logic corresponds to a non Boolean (nondistributive) partition logic isomorphic to MO2. Of course, if one develops the automaton further, then, for instance, v(2222)={{1},{2},{3}}, and the classical case is recovered [notice that this is not the case for v([ · || 1])=v(1)]. Yet, if one assumes that the output is channelled away into the interface after only a single evolution step (and that afterwards the evolution is via another U), the nonclassical feature pertains despite the bijective character of the evolution.

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].

References

[1]
Benacerraf, P. Tasks and supertasks, and the modern Eleatics. Journal of Philosophy LIX, 24 (1962), 765-784.

[2]
Bennett, C. H. Logical reversibility of computation. IBM Journal of Research and Development 17 (1973), 525-532. Reprinted in [38,pp. 197-204].

[3]
Bennett, C. H. The thermodynamics of computation-a review. In International Journal of Theoretical Physics [38], pp. 905-940. Reprinted in [38,pp. 213-248].

[4]
Berman, A., and Plemmons, R. J. Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York, 1979.

[5]
Beth, E. W. The Foundations of Metamathematics. North-Holland, Amsterdam, 1959.

[6]
Brauer, W. Automatentheorie. Teubner, Stuttgart, 1984.

[7]
Brillouin, L. Science and Information, second edition ed. Academic Press, New York, 1962.

[8]
Brillouin, L. Scientific Uncertainty and Information. Academic Press, New York, 1964.

[9]
Calude, C. Information and Randomness-An Algorithmic Perspective. Springer, Berlin, 1994.

[10]
Calude, C., Calude, E., Svozil, K., and Yu, S. Physical versus computational complementarity I. International Journal of Theoretical Physics 36, 7 (1997), 1495-1523.

[11]
Caves, C. M. Quantum limits on noise in linear amplifiers. Physical Review D26 (1982), 1817-1839.

[12]
Chaitin, G. J. Information-Theoretic Incompleteness. World Scientific, Singapore, 1992.

[13]
Conway, J. H. Regular Algebra and Finite Machines. Chapman and Hall Ltd., London, 1971.

[14]
Davis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.

[15]
Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society London A 400 (1985), 97-119.

[16]
Earman, J., and Norton, J. D. Forever is a day: supertasks in Pitowsky and Malament-Hogart spacetimes. Philosophy of Science 60 (1993), 22-42.

[17]
Ekert, A., and Jozsa, R. Quantum computation and Shor's factoring algorithm. Reviews of Modern Physics 68, 3 (1996), 733-753.

[18]
Feld, B. T., and Szilard, G. W. The Collected Works of Leo Scilard: Scientific Papers. MIT Press, Cambridge, 1972.

[19]
Fredkin, E., and Toffoli, T. Conservative logic. International Journal of Theoretical Physics 21 (1982), 219-253.

[20]
Glauber, R. J. Amplifiers, attenuators and the quantum theory of measurement. In Frontiers in Quantum Optics, E. R. Pikes and S. Sarkar, Eds. Adam Hilger, Bristol, 1986.

[21]
Grünbaum, A. Modern Science and Zeno's paradoxes, second edition ed. Allen and Unwin, London, 1968.

[22]
Grünbaum, A. Philosophical Problems of Space of Time, second, enlarged edition ed. D. Reidel, Dordrecht, 1973.

[23]
Herbert, N. FLASH-a superluminal communicator based upon a new kind of quantum measurement. Foundation of Physics 12, 12 (1982), 1171-1179.

[24]
Hogarth, M. Predicting the future in relativistic spacetimes. Studies in History and Philosophy of Science. Studies in History and Philosophy of Modern Physics 24, 5 (1993), 721-739.

[25]
Hogarth, M. Non-Turing computers and non-Turing computability. PSA 1 (1994), 126-138.

[26]
Kirk, G. S., and Raven, J. E. The Presocratic Philosophers. Cambridge University Press, Cambridge, 1957.

[27]
Kreisel, G. A notion of mechanistic theory. Synthese 29 (1974), 11-16.

[28]
Landauer, R. Fundamental physical limitations of the computational process; an informal commentary. Cybernetics Machine Group Newsheet (1/1/1987).

[29]
Landauer, R. Irreversibility and heat generation in the computing process. In IBM Journal of Research and Development [38], pp. 183-191. Reprinted in [38,pp. 188-196].

[30]
Landauer, R. Wanted: a physically possible theory of physics. IEEE Spectrum 4 (1967), 105-109.

[31]
Landauer, R. Uncertainty principle and minimal energy dissipation in the computer. International Journal of Theoretical Physics 21 (1982), 283-297.

[32]
Landauer, R. Dissipation and noise immunity in computation and communication. Nature 335 (1988), 779-784.

[33]
Landauer, R. Computation, measurement, communication and energy dissipation. In Selected Topics in Signal Processing, S. Haykin, Ed. Prentice Hall, Englewood Cliffs, NJ, 1989, p. 18.

[34]
Landauer, R. Information is physical. Physics Today 44 (May 1991), 23-29.

[35]
Landauer, R. Advertisement for a paper I like. In On Limits, J. L. Casti and J. F. Traub, Eds. Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994, p. 39.

[36]
Landauer, R. Zig-zag path to understanding. In Proceedings of the Workshop on Physics and Computation PHYSCOMP '94 (Los Alamitos, CA, 1994), IEEE Computer Society Press, pp. 54-59.

[37]
Lee, H. D. P. Zeno of Elea. Cambridge University Press, Cambridge, 1936. reprinted by Adolf M. Hakkert, Amsterdam, 1967.

[38]
Leff, H. S., and Rex, A. F. Maxwell's Demon. Princeton University Press, Princeton, 1990.

[39]
López-Escobar, E. G. K. Zeno's paradoxes pre Gödelian incompleteness. Jahrbuch 1991 der Kurt-Gödel-Gesellschaft (1991), 49.

[40]
Mandel, L. Is a photon amplifier always polarization dependent? Nature 304 (1983), 188.

[41]
Milonni, P. W., and Hardies, M. L. Photons cannot always be replicated. Physics Letters 92A, 7 (1982), 321-322.

[42]
Moore, E. F. Gedanken-experiments on sequential machines. In Automata Studies, C. E. Shannon and J. McCarthy, Eds. Princeton University Press, Princeton, 1956.

[43]
Odifreddi, P. Classical Recursion Theory. North-Holland, Amsterdam, 1989.

[44]
Pitowsky, I. The physical Curch-Turing thesis and physical computational complexity. Iyyun 39 (1990), 81-99.

[45]
Rogers, Jr., H. Theory of Recursive Functions and Effective Computability. MacGraw-Hill, New York, 1967.

[46]
Rosen, R. Effective processes and natural law. In The Universal Turing Machine. A Half-Century Survey, R. Herken, Ed. Kammerer & Unverzagt, Hamburg, 1988, p. 523.

[47]
Rucker, R. Infinity and the Mind. Birkhäuser, Boston, 1982. Reprinted by Bantam Books, 1986.

[48]
Schaller, M., and Svozil, K. Automaton logic. International Journal of Theoretical Physics 35, 5 (May 1996), 911-940.

[49]
Schrödinger, E. Die gegenwärtige Situation in der Quantenmechanik. Naturwissenschaften 23 (1935), 807-812, 823-828, 844-849. English translation in [60,pp. 152-167].

[50]
Schrödinger, E. Mein Leben, meine Weltansicht. Zsolnay, Vienna, 1985. English translation: My view of the world, Cambridge University Press, Cambridge, 1964.

[51]
Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium of on Foundations of Computer Science, Santa Fe, NM, Nov. 20-22, 1994 (November 1994), IEEE Computer Society Press.
e-print http://xxx.lanl.gov/abs/quant-ph/9508027.

[52]
Siegelmann, H. T. Computation beyond the Turing limit. Science 268 (1995), 545-548.

[53]
Svozil, K. Randomness & Undecidability in Physics. World Scientific, Singapore, 1993.

[54]
Svozil, K. A constructivist manifesto for the physical sciences. In The Foundational Debate, Complexity and Constructivity in Mathematics and Physics (Dordrecht, Boston, London, 1995), W. D. Schimanovich, E. Köhler, and F. Stadler, Eds., Kluwer, pp. 65-88. Cf. [57].

[55]
Svozil, K. On the computational power of physical systems, undecidability, the consistency of phenomena and the practical uses of paradoxa. In Fundamental Problems in Quantum Theory: A Conference Held in Honor of Professor John A. Wheeler. Annals of the New York Academy of Sciences 755 (1995), D. M. Greenberger and A. Zeilinger, Eds., New York Academy of Sciences, pp. 834-841.

[56]
Svozil, K. Set theory and physics. Foundations of Physics 25 (1995), 1541-1560.

[57]
Svozil, K. How real are virtual realities, how virtual is reality? The constructive re-interpretation of physical undecidability. Complexity 1, 4 (1996), 43-54.

[58]
Thomson, J. F. Tasks and supertasks. Analysis 15 (October 1954), 1-13.

[59]
Weyl, H. Philosophy of Mathematics and Natural Science. Princeton University Press, Princeton, 1949.

[60]
Wheeler, J. A., and Zurek, W. H. Quantum Theory and Measurement. Princeton University Press, Princeton, 1983.

[61]
Wooters, W. K., and Zurek, W. H. A single quantum cannot be cloned. Nature 299 (1982), 802-803.



File translated from TEX by TTH, version 3.02.
On 3 Jun 2002, 15:35.