On the computational power of physical systems, undecidability, the consistency of phenomena and the practical uses of paradoxa

K. Svozil
Institut für Theoretische Physik
Technische Universität Wien
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
e1360dab@awiuni11.edvz.univie.ac.at

Abstract

Undecidability in mathematics comes in different varieties; so does undecidability in physics. In physics we have to make sure that the theory is a suitable formal representation of the phenomenology. For example, if the outcome of an experiment cannot be predicted, does that mean that ``God plays dice?'' Or does it mean that although the causes are in principle known, we are unable to compute a prediction? Or does it simply mean that there are causes but these are unknown to us? These questions may never be fully settled [1], but since Gödel's [2] and Turing's [4] centennial findings, remarkable advances have been made in the formal perception of undecidability. And today's computers not only serve as number crunchers but are becoming a medium to ``virtual'' realities. This greatly promotes the interaction between theoretical computer sciences, formal logic and the physics of ``real'' reality.

Let us briefly consider the physical correspondents of two forms of mathematical undecidability, the first being associated with the assumption of the continuum (oracle computation), the second arising in the context of finite computation. If one wishes to order theories with respect to the computational power necessary to implement them, continuum theories require more resources than theories based on universal computation (e.g., Cellular Automata [5,6,7]), which in turn are more powerful than finite models.

Continuum theories require the generation, storage and processing of numbers which are uncomputable in the sense of Turing. More precisely (and worse), ``almost all'' (with probability one) elements of the continuum ``urn'' must be represented by random sequences; stated pointedly: any bit in its binary expansion is as uncorrelated to the previous and the following bits as is any toss of a fair coin from other tosses [8,9]. In continuum theories, ``God plays dice.'' In such theories, undecidability, as not caused otherwise, is implemented by absolute randomness. How come then, one may ask, that classical mechanics has been long considered as the prototype for a ``deterministic'' model? The reason for this is twofold: First, one may conjecture that it is possible to keep all the nice features of continuum mechanics (e.g., calculus) while at the same time get rid of the nasty aspects (e.g., nonconstructive randomness); and indeed there are indications that this might be possible [10]. Second, there are ``nonchaotic'' dynamical systems, in which arbitrary initial conditions yield solutions which converge rapidly toward periodic behaviour, or at least converge toward a computable function (attractor).

Continuum theory (any dense set) allows the construction of ``infinity machines,'' which could serve as oracles for the halting problem. Their construction closely follows Zeno's paradox of Achilles and the Tortoise (Hector) by squeezing the time it takes for successive steps of computation t with geometric progression:

Picture Omitted
    I.e., the time necessary for the n'th step becomes t(n) = kⁿ, k < 0. The limit of infinite computation is then reached in finite physical time

lim_{N® ¥}å_{n = 1}^N t(n) = lim_{N® ¥}å_{n = 1}^N kⁿ = 1/(1-k). It can be shown by a diagonalization argument that the application of such oracle subroutines would result in a paradox in classical physics (cf. [11], p. 24, 114). Therefore, at least in this example, too powerful physical models (of computation) are inconsistent.

A second type of undecidability which occurs in finite systems is computational complementarity, which is realizable already at a very elementary pre-diagonalization level [12]; i.e., without the requirement of computational universality or its arithmetic equivalent. The resulting ``static'' automaton logic has great similarities to quantum logic [13,11].

Our major concern here shall be a third type of undecidability. It will be demonstrated how diagonalization techniques lead to the exclusion of time paradoxa, and how quantum physics implements causality.

Classical information theory (e.g., [14]) is based on the bit as fundamental atom. This classical bit, henceforth called cbit, is physically represented by one of two classical states. It is customary to use the symbols ``0'' and ``1'' as the names of these states. The corresponding classical computational basis is {0,1} = \Bbb Z₂.

In quantum information theory (cf. [15,16,17,18,19,20,21,22]), the most elementary unit of information, henceforth called qbit, may be physically represented by a coherent superposition of the two states which correspond to the symbols 0 and 1. The corresponding quantum computational basis is the undenumerable set

{ |a,bñ\mid |a,bñ = a|0ñ+b|1ñ,  |a|²+|b|² = 1,  a,b Î \Bbb C }.

In what follows we shall consider the hypothetical transmission of information backward in time. To be more specific, we shall use an EPR-type telegraph which uses entangled particles in a singlet state (i.e., the total angular momentum of the two particles is zero) as drawn in Fig. 1.

The apparatus is tuned to convey perfect correlations of the direction of angular momentum labelled by ``+'' and ``-''; i.e., the outcomes are either + + or - -. Perfect correlations can be achieved by choosing a relative angle of measurement of p. The (unphysical) assumption necessary for signalling backwards in time is that on one side, say for particles in path 1, the outcome can be controlled. This means that it will be assumed possible to produce a particle with, say, direction of angular momentum ``+'' (``-'') in the path 1 at t_A, thereby transmitting a signal ``+'' (``-'') via its perfectly correlated entangled partner in path 2 to a second observer back in time at t_B; thereby, t_A > t_B > t_S but otherwise arbitrary.

An alternative setup for information transmission backward in time by an EPR-type quantum telegraph would use the stronger-than-classical correlations for relative measurement angles not equal to 0, p/2 and p. In this case, the (unphysical) assumption necessary for signalling backwards in time is the outcome dependence on one side, say for particles in path 2, on the angle chosen for measurements on beam 1 (e.g., by ``cloning,'' cf. [23,24,25,26,27]).

Of course, this kind of outcome control or outcome dependence would neither be allowed in relativistic mechanics nor in quantum mechanics. The stronger-than-classical quantum expectation functions are often considered manifestations of ``nonlocality'' [28] (or, alternatively, of failure of classical probability theory [29]), but they only effect parameter dependence, not outcome dependence of single events [30,31].

We shall make use of the EPR-type telegraph to construct a time paradox and argue against outcome predictability and outcome controllability in any form. In a similar manner, the liar paradox [32] was translated by Gödel into arithmetic [2] to argue against a complete description of a formal system within that very system [36]. For instance, the gödelian sentence [37] claiming its own unprovability in a particular system appears undecidable within that very system. In physical terms, undecidability must be translated onto the level of phenomena and, only in a secondary step, into their theoretic description. On the phenomenological level there is no such thing as an inconsistent phenomenon. In a typical yes-no experiment which can have two possible outcomes, only one of these outcomes will actually be measured. However, this uniqueness of phenomenology does not guarantee that a theory exists which predicts it completely. There might even be a ``meta-physical'' (extrinsic [38], exo- [39]) arena in which this particular outcome could be deterministically accounted for. Yet, for an intrinsic observer who is embedded in the system [40], this ``meta-physical'' level might be permanently inaccessible [41,11]. As will be shown below, quantum mechanics implements this phenomenological undecidability both by the postulate of randomness of certain outcomes and by the superposition principle. Related arguments have been put forward in [37,42,43,44,45,46,47].

Consider two backward-in-time signalling EPR-type telegraphs of the above type arranged as drawn in Fig. 2. Physically, the flow of information is mediated via the two entangled pairs in paths 1-2 and 3-4. An information in 2 is mirrored by M in 3. By this instrument, some mechanistic agent A (e.g., computer, deterministic observer) which is given the power of outcome control can exchange information with itself on closed timelike lines [34,35]. Agent A shall be confronted with the following paradoxical task.

Whenever A registers the information ``+'' (``-'') at time t_A¢, A must stimulate the opposite outcome ``-'' (``+'') at the later time t_A.

Before discussing the paradox, let us consider the two states |0ñ º ``-'' and |1ñ º ``+'' which are accessible to A. These states can be the basis of a cbit with the identification of the symbols ``0'' and ``1'' for |0ñ and |1ñ, respectively. Quantum mechanically any coherent superposition of them is allowed. Agent A's paradoxical task can be formalized by a unitary evolution operator

[^D] as follows

[^D] will be called diagonalization operator, despite the fact that its only nonvanishing components are off-diagonal. (Notice that A's task would be perfectly consistent if there were no ``bit switch'' and if thus

[^D] = \Bbb I.)

The paradoxical feature of the construction reveals itself in the following question: what happens to agent A? In particular: what does A register and send?

Let us first consider these questions from a classical perspective. Classically, the particles with which A operates can only be in one of two possible states, namely in |0ñ or in |1ñ, corresponding to the classical computational basis \Bbb Z₂. By measuring the particle in beam 4, A gets either the outcome ``+'' or ``-''. In both cases, agent A is lead to a complete contradiction.

For, if A receives ``+'', corresponding to cbit state 1, A is obliged to send out ``-'', corresponding to cbit state 0 (A has been assumed to be able to control the outcomes in beam 1). Due to the perfect EPR-correlations, the partner particle in beam 2 is registered as ``-'' at the mirror at time t<sub>B</sub>. By controlling the outcome in beam 3, this mirrored cbit can again be sent backwards in time, where ``-'' is received by A via a measurement of the particle in beam 4. This, however, contradicts the initial assumption that the outcome in beam 4 is ``+''.

On the other hand, if A receives ``-'', corresponding to cbit state 0, A is obliged to send out ``+'', corresponding to cbit state 1; yet, since at t_B the cbit is just reflected as described above, A should have received ``+''. Thus classically, agent A is in an inescapable dilemma.

The defense strategy in formal logic and classical recursion theory against such inconsistencies is to avoid the appearance of a paradox by claiming (stronger: requiring) overall consistency, resulting in no-go theorems; i.e., in the postulate of the impossibility of any operational method, procedure or device which would have the potentiality to cause a paradox. (Among the many impossible objects giving rise to paradoxes are such seemingly innocent devices as a ``halting algorithm'' computing whether or not another arbitrary computable algorithm produces a particular output; or an algorithm identifying another arbitrary algorithm by input-output experiments.)

In the above case, the defense strategy would result in the postulate of the impossibility of any backward-in-time information flow or, more general, of closed timelike lines. Since the only nontrivial feature of the backward-in-time information flow has been outcome controllability or outcome dependence, the diagonalization argument can be used against outcome controllability and outcome dependence, resulting in an intrinsic randomness of the individual outcomes.

Quantum mechanics implements exactly that kind of recursion theoretic argument; yet in a form which is not common in recursion theory. Observe that the paradox is resolved when A is allowed a nonclassical qbit of information. In particular, agent A's task can consistently be performed if it inputs a qbit corresponding to the fixed point state of [^D]; i.e.,

We close the discussion on the consistent use of paradoxa in physics with a few comments. First, it is important to recognize that the above considerations have no immediate bearing on quantum complementarity. In the author's opinion, complementarity is a general feature of the intrinsic perception of computer-generated universes, which is realizable already at a very elementary pre-diagonalization level [12,13,11]; i.e., without the requirement of computational universality or its arithmetic equivalent.

Second, the above argument remains valid for any conceivable (local or nonlocal [51,29]) hidden variable theory. The consistency of the physical phenomenology requires that hidden variables remain inaccessible to an intrinsic observer. From an intrinsic, operational point of view, a paradox always marks the appearance of uncertainty and uncontrollability.

Third, an application for quantum information theory is the handling of inconsistent information in databases. Thereby, two contradicting cbits of information |añ and |bñ are resolved by the qbit

|¹/₂,¹/₂ ñ = (1/ Ö2)(|añ+ |bñ). Throughout the rest of the computation the coherence is maintained. After the processing, the result is obtained by a measurement. The processing of qbits requires an exponential space overhead on classical computers in cbit base [7]. Thus, in order to remain tractable, the corresponding qbits should be implemented on truly quantum universal computers.

References

[1]

Ph. Frank, Das Kausalgesetz und seine Grenzen (Springer, Vienna 1932).

[2]

K. Gödel, Monatshefte für Mathematik und Physik 38, 173 (1931); English translation in [3].

[3]

K. Gödel, Collected Works, Volume I, Publications 1929-1936, ed. by S. Feferman, J. W. Dawson, Jr., St. C. Kleene, G. H. Moore, R. M. Solovay, J. van Heijenoort (Oxford University Press, Oxford, 1986).

[4]

A. M. Turing, Proc. London Math. Soc. (2), 42, 230 (1936-7).

[5]

E. Fredkin, International Journal of Theoretical Physics 21, 219 (1982); Physica D45, 254 (1990).

[6]

T. Toffoli and N. Margolus, Cellular Automata Machines (MIT Press, Cambridge, Massachusetts, 1987).

[7]

R. P. Feynman, International Journal of Theoretical Physics 21, 467 (1982).

[8]

G. J. Chaitin, Int. J. Theoret. Physics 21, 941 (1982); reprinted in G. J. Chaitin, Information, Randomness and Incompleteness, Second edition (World Scientific, Singapore, 1987, 1990).

[9]

C. Calude, Information and Randomness - An Algorithmic Perspective (Springer, Berlin, 1994).

[10]

E. Bishop and D. S. Bridges, Constructive Analysis (Springer, Berlin, 1985).

[11]

K. Svozil, Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).

[12]

E. F. Moore, Gedanken-Experiments on Sequential Machines, in Automata Studies, ed. by C. E. Shannon & J. McCarthy (Princeton University Press, Princeton, 1956).

[13]

D. Finkelstein and S. R. Finkelstein, International Journal of Theoretical Physics 22, 753 (1983).

[14]

R. W. Hamming, Coding and Information Theory, Second Edition (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).

[15]

D. Z. Albert, Phys. Lett. 94A, 249 (1983).

[16]

D. Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985).

[17]

R. P. Feynman, Opt. News 11, 11 (1985).

[18]

A. Peres, Phys. Rev. A32, 3266 (1985).

[19]

P. Benioff, Annals New York Akademy of Sciences 480, 475 (1986).

[20]

N. Margolus, Annals New York Akademy of Sciences 480, 487 (1986).

[21]

D. Deutsch, Proc. R. Soc. Lond. A 425, 73 (1989).

[22]

D. Deutsch and R. Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992).

[23]

N. Herbert, Foundation of Physics 12, 1171 (1982).

[24]

W. K. Wooters and W. H. Zurek, Nature 299, 802 (1982).

[25]

P. W. Milonni and M. L. Hardies, Phys. Lett. 92A, 321 (1982).

[26]

L. Mandel, Nature 304, 188 (1983).

[27]

R. J. Glauber, Amplifyers, Attenuators and the Quantum Theory of Measurement, in Frontiers in Quantum Optics, ed. by E. R. Pikes and S. Sarkar (Adam Hilger, Bristol 1986).

[28]

J. S. Bell, Physics 1, 195 (1964); J. S. Bell, Speakable and Unspeakable in Quantum Mechanics (Cambridge University Press, Cambridge, 1987).

[29]

I. Pitowsky, Quantum Probability - Quantum Logic (Springer, Berlin, 1989).

[30]

A. Shimony, Controllable and uncontrollable non-locality, in Proc. Int. Symp. Foundations of Quantum Mechanics, ed. by S. Kamefuchi et al. (Physical Society of Japan, Tokyo, 1984).

[31]

A. Shimony, Events and Processes in the Quantum World, in Quantum Concepts in Space and Time, ed. by R. Penrose and C. I. Isham (Clarendon Press, Oxford, 1986).

[32]

The Bible contains a passage, which refers to Epimenides, a Crete living in the capital city of Cnossus: ``One of themselves, a prophet of their own, said, `Cretans are always liars, evil beasts, lazy gluttons.' '' - St. Paul, Epistle to Titus I (12-13). For more details, see A. R. Anderson, St. Paul's epistle to Titus, in The Paradox of the Liar, ed. by R. L. Martin (Yale University Press, New Haven, 1970).

[33]

M. Davis, The Undecidable (Raven Press, New York, 1965).

[34]

K. Gödel, Rev. Mod. Phys. 21, 447 (1949): K. Gödel, A remark about the relationship between relativity theory and idealistic philosophy, in Albert Einstein, philosopher-scientist, ed. by P. A. Schilpp (Evanston, Ill., 1949), p. 555.

[35]

D. Deutsch, Phys. Rev. D44, 3197 (1991).

[36]

The following citation is taken from K. Gödel's reply to a letter by A. W. Burks, reprinted in J. von Neumann's Theory of Self-Reproducing Automata, ed. by A. W. Burks (University of Illinois Press, Urbana, 1966), p. 55; see also S. Feferman, Philosophia Naturalis 21, 546 (1984), p. p. 554:

``¼ the fact that a complete epistemological description of a language A cannot be given in the same language A, because the concept of truth of sentences of A cannot be defined in A. It is this theorem which is the true reason for the existence of undecidable propositions in the formal systems containing arithmetic.''

[37]

K. R. Popper, The British Journal for the Philosophy of Science 1, 117, 173 (1950).

[38]

K. Svozil, Europhysics Letters 2, 83 (1986); Il Nuovo Cimento 96B, 127 (1986); and [11], chapter 6.

[39]

O. E. Rössler, Endophysics, in Real Brains, Artificial Minds, ed. by J. L. Casti and A. Karlquist (North-Holland, New York, 1987), p. 25; O. E. Rössler, Endophysics, Die Welt des inneren Beobachters, ed. by P. Weibel (Merwe Verlag, Berlin, 1992).

[40]

T. Toffoli, The role of the observer in uniform systems, in Applied General Systems Research, ed. by G. Klir (Plenum Press, New York, London, 1978).

[41]

The observer is situated, in O. E. Rössler's dictum, in a ``Cartesian prison;'' cf. H. Atmanspacher and G. Dalenoort, eds., Inside Versus Outside (Springer, Berlin, 1994), p. 156.

[42]

J. Rothstein, International Journal of Theoretical Physics 21, 327 (1982).

[43]

A. Peres, Foundation of Physics 15, 201 (1985).

[44]

St. Wolfram, Physical Review Letters 54, 735 (1985); Physica D10, 1 (1984); Rev. Mod. Phys. 55, 601 (1983).

[45]

Ch. D. Moore, Phys. Rev. Lett. 64, 2354 (1990); cf. Ch. Bennett, Nature 346, 606 (1990).

[46]

A. C. Elitzur, Phys. Lett. A167, 335 (1992), as well as S. Popescu and D. Rohrlich, Foundations of Physics 24, 379 (1994) refer to a talk of Professor Y. Aharonov delivered at the Einstein centennial.

[47]

A. Posiewnik, On inconsistency of the language of physics (University of Gdansk preprint, 1993).

[48]

H. Rogers, Theory of Recursive Functions and Effective Computability (MacGraw-Hill, New York 1967).

[49]

P. Odifreddi, Classical Recursion Theory (North-Holland, Amsterdam, 1989).

[50]

In an abstract form, the above argument is the analogon to the fixed point or paradoxical combinator in combinatory logic; cf. H. B. Curry and R. Feys, Combinatory Logic (North-Holland, Amsterdam, 1958), p. 151, 178 and H. P. Barendregt, The Lambda Calculus (Revised Edition) (North Holland, Amsterdam, 1984).

[51]

I. Pitowsky, Phys. Rev. Lett. 48, 1299 (1982); Phys. Rev. D27, 2316 (1983); N. D. Mermin, Phys. Rev. Lett. 49, 1214 (1982); A. L. Macdonald, Ibid., 1215 (1982); I. Pitowsky, Ibid., 1216 (1982).