The purpose of this talk is to single out some physical assumptions that commonly underpin physical computation, several models of computation (discrete and continuous) as well as the notion of "algorithm" itself. In particular, it is argued that scientific representation is inextricably intertwined with physical computation, and so necessary conditions for the former are also necessary conditions for the latter (and for computation in general). I discuss some physical situations where such conditions are violated and show that uncomputability results arise in such situations as well.
The purpose of this talk is to single out some physical assumptions that commonly underpin physical computation, several models of computation (discrete and continuous) as well as the notion of "algorithm" itself. In particular, it is argued that scientific representation is inextricably intertwined with physical computation, and so necessary conditions for the former are also necessary conditions for the latter (and for computation in general). I discuss some physical situations where such conditions are violated and show that uncomputability results arise in such situations as well.
This thesis is a collection of three case studies, investigating various sources of indeterminism and undecidability as they bear upon in principle unpredictability of the behaviour of mechanistic systems in both classical and quantum physics. I begin by examining the sources of indeterminism and acausality in classical physics. Here I discuss the physical significance of an often overlooked and yet important Lipschitz condition, the violation of which underlies the existence of anomalous non-trivial solutions in the Norton-type indeterministic systems. I argue that the singularity arising from the violation of the Lipschitz condition in the systems considered appears to be so fragile as to be easily destroyed by slightly relaxing certain (infinite) idealizations required by these models. In particular, I show that the idealization of an absolutely nondeformable, or infinitely rigid, dome appears to be an essential assumption for anomalous motion to begin; any slightest elastic deformations of the dome due to finite rigidity of the dome destroy the shape of the dome required for indeterminism to obtain. I also consider several modifications of the original Norton's example and show that indeterminism in these cases, too, critically depends on the nature of certain idealizations pertaining to elastic properties of the bodies in these models. As a result, I argue that indeterminism of the Norton-type Lipschitz-indeterministic systems should rather be viewed as an artefact of certain (infinite) idealizations essential for the models, depriving the examples of much of their intended metaphysical import, as, for example, in Norton's antifundamentalist programme. Second, I examine the predictive computational limitations of a classical Laplace's demon. I demonstrate that in situations of self-fulfilling prognoses the class of undecidable propositions about certain future events, in general, is not empty; any Laplace's demon having all the information about the world now will be unable to predict all the future. In order to answer certain questions about the future it needs to resort occasionally to, or to consult with, a demon of a higher order in the computational hierarchy whose computational powers are beyond that of any Turing machine. In computer science such power is attributed to a theoretical device called an Oracle--a device capable of looking through an infinite domain in a finite time. I also discuss the distinction between ontological and epistemological views of determinism, and how adopting Wheeler-Landauer view of physical laws can entangle these aspects on a more fundamental level. Thirdly, I examine a recent proposal from the area of quantum computation purporting to utilize peculiarities of quantum reality to perform hypercomputation. While the current view is that quantum algorithms (such as Shor's) lead to re-description of the complexity space for computational problems, recently it has been argued (by Kieu) that certain novel quantum adiabatic algorithms may even require reconsideration of the whole notion of computability, by being able to break the Turing limit and "compute the non-computable". If implemented, such algorithms could serve as a physical realization of an Oracle needed for a Laplacian demon to accomplish its job. I critically review this latter proposal by exposing the weaknesses of Kieu's quantum adiabatic demon, pointing out its failure to deliver the purported hypercomputation. Regardless of whether the class of hypercomputers is non-empty, Kieu's proposed algorithm is not a member of this distinguished club, and a quantum computer powered Laplace's demon can do no more than its ordinary classical counterpart.
The study of electrical currents in a regime where a description as a continuous flow fails and the particle nature becomes important, but where notions such as particle density or currents continue to be meaningful, will be at the heart of the present dissertation. Given such a mesoscopic system through which electrons flow, either actively through quantum pumping or passively due to a potential difference, we investigate quantities such as transferred charge, noise, current fluctuations, and relations between them. More generally we shall examine the statistics of particle transport. All discussions will concentrate on compact devices transferring charge between two one-dimensional reservoirs (the leads) of independent electrons. Firstly, we consider the generating function of the moments of transferred charge and we prove that it is given by the determinant of a single-particle operator. It is formally equivalent to a formula of Lesovik and Levitov, but is shown to be well-defined in the situations under consideration, whereas the former is not, in general. The mechanism leading to regularization is typical for mesoscopic systems: we consider a limiting case that reveals the fundamental structure of the problem. In fact, as suited for an open system, the leads contain an infinite number of charges. It follows mathematically that the second quantization ought to be carried out upon the Fermi sea and not upon the vacuum, a procedure known as the GNS construction. We shall rely heavily on operator algebraic techniques. The set of observables, the C*-algebra of canonical anticommutation relations, admits different representations for systems in the thermodynamic limit, which are described by their reduced one-particle density matrix. An important question will be the existence of operators such as the charge or the time evolution in a given representation, which induce so-called Bogoliubov transformations. These prerequisites at hand, we shall pose the problem of counting statistics clearly, prove that the regularized determinant emerges naturally, and show that it describes the transport of integer charges with non-negative probabilities. Secondly, we introduce a model of instantaneous scattering in which various examples can be computed explicitely. In particular, we show that the above theorem applies for scattering through a smoothly operating pump over a finite time interval. We also exhibit situations where the propagator does exist but the generating function is ambiguous. In a more computational approach, we then turn to the relation of individual moments of transferred charge to current correlators. It turns out that the former can indeed be expressed as integrals of the latter over time, provided the current operators are ordered according to Matthews’ T∗ ordering. It is given by first arranging the charge operators according to their time indices, and only then taking the time derivatives, which induce contact terms whose singular support lies along time coincidences. We shall give two derivations of this result, because the first one is transparent, and the second one is related to contradictory computations in the literature where the system is considered to be measured by an external spin. In the model of constant instantaneous scattering, we then argue from the Lesovik-Levitov determinant that the transport can be interpreted in terms of a binomial process in the long time limit. In a parallel computation, we concentrate on the third cumulant as defined by integration of current correlators and show how the contact terms of the T∗ ordering play an essential role in providing the expected binomial result, too. To close this thesis, we suggest an algebraic framework that lays the foundations for a rigorous discussion of the Casimir effect. The problem of infinites arising in the comparison of two physical situations for a bosonic field is interpreted as the non-equivalence of states on the algebra of canonical commutation relations. We exhibit sufficient conditions on the one-particle Hamiltonians which ensure that the Casimir energy is finite and give an expression for it. We discuss its formal equivalence with the result obtained from the standard mode summing method.
Many of the fundamental limits on information processing, from thermodynamics, relativity, and quantum mechanics, are only a few decades away. Novel physically motivated computing paradigms, such as reversible computing and quantum computing, may help in certain ways, but even they remain subject to some basic limits. One can arrive at several firm conclusions regarding upper bounds on the limits of computing. In this article, the author only reviews the fundamental technology-independent limits.
Necessary and sufficient conditions are given for a quantummechanical system to possess a coordinate system with respect to which its behaviour at discrete times is that of a universal digital computer. The form of the diagonal representation for the unitary time evolution operator for quantum universal computers is derived; aspects of the transformation between the diagonal representation and the computational representation are shown to be uncomputable. A quantum-mechanical treatment of macroscopic, dissipative computers is given.
Quantum physics is a fascinating area from a computational viewpoint. The features that make quantum systems prohibitively hard to simulate classically are precisely the aspects exploited by quantum computation to obtain exponential speedups over classical computers. In this talk I will survey our current understanding of the power (and limits) of quantum computers, and prospects for experimentally realizing them in the near future. I will also touch upon insights from quantum comuptation that have resulted in new classical algorithms for efficient simulation of certain important quantum systems.