Consider the classical model of a Turing machine with an oracle. The classical oracle is a one step external consultation device. The oracle may contain either non-computable information, or computable information provided just to speed up the computations of the Turing machine. In this talk we will consider the abstract experimenter (e.g. the experimental physicist) as a Turing machine and the abstract experiment of measuring a physical quantity (using a specified physical apparatus) as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. It is standard to consider that to measure a real number 4 µ, e.g. the value of a physical quantity, the experimenter (now the Turing machine) should proceed by approximations. Thus, besides the value of µ, we will consider dyadic rational approximations (denoted by finite binary strings), and a procedure to measure µ proved to be universal.
Consider the classical model of a Turing machine with an oracle. The classical oracle is a one step external consultation device. The oracle may contain either non-computable information, or computable information provided just to speed up the computations of the Turing machine. In this talk we will consider the abstract experimenter (e.g. the experimental physicist) as a Turing machine and the abstract experiment of measuring a physical quantity (using a specified physical apparatus) as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. It is standard to consider that to measure a real number 4 µ, e.g. the value of a physical quantity, the experimenter (now the Turing machine) should proceed by approximations. Thus, besides the value of µ, we will consider dyadic rational approximations (denoted by finite binary strings), and a procedure to measure µ proved to be universal.
In this work we proceed with the investigation of the power of an abstract model of computation that considers Turing machines coupled with physical oracles. A physical oracle is an experiment controlled by the Turing machine with the purpose of measuring some quantity or parameter, possibly suitable to boost the power of the Turing machine. We consider one of the three known types of measurement experiments — the two-sided case. Researches on the computational power under bounded resources of the two other types — threshold and vanishing — have been considered and are settle by other authors up to some hard open problems. Herein we address the unfinished case of the two-sided oracle, establishing the corresponding upper bounds. We consider three types of communication between the Turing machine and the oracle (infinite precision, unbounded precision and fixed precision), that simulate the error propagation common to physical experiments. These three types of precision introduce variants of the two-sided oracle machines. We fix the upper bounds for the three cases. In the context of the infinite precision protocol of two-sided machines, we then address the question of knowing if a number, a physical parameter, is measurable or not. This problem was first put out by the physicists Geroch and Hartle without a formal framework to reason upon definition. We characterize the measurable and the non measurable numbers and we analyze some of their properties.
We apply algorithmic information theory to quantum mechanics in order to shed light on an algorithmic structure which is inherent in quantum mechanics.There are two equivalent ways to define the (classical) Kolmogorov ∞mplexityK(s) of agiven classical finite binary string s .In the standard way, K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output s .In the other way, we first introduce the so-called universal probability m , and then define K(s) as −log2m(s) without using the concept of program-size.We generalize the universal probability to amatrix-valued function, and identify this function with apositive operator-valued measure (POVM), which describes the statistics of outcomes in aquantum measurement in the general set- ting.Based on this identification, we study acomputable POVM measurement with countable measurement outcomes performed upon afinite dimensional quantum system.We show that, up to amultiplicative constant, 2−K(s) is the upper bound for the probability of each measurement outcome s in such aquantum measurement.In what follows, the upper bound 2−K(s) is shown to be optimal in acertain sense.
Abstract. Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP-complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete subphysical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor's quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper-bounded. If this bound is associated with the quantum-classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
Computation is a process of performing a large number of simple operations. The main building blocks of classical computers are bits. Each of them can take either the value 0 or 1. A series of gates can change these values by acting on them selectively. This process is structured to fulfil a purpose. For example, if we are interested in adding two numbers, the numbers are encoded into bits and gates are performed such that the final state of the bits reveals the desired answer: a number which is the sum of the initial ones. While it is possible to build algorithms that can perform almost any computation, it is also desirable to find the answer within a reasonable length of time or with a reasonable amount of resources. There is an ever-growing demand in computational power for both scientific and commercial purposes. Indeed, it is surprisingly easy to find an application that can jam even the fastest computer. This fuels a vast effort in the research of information science to increase the speed and processing power of computers. Modern computational models are based on the universal Turing machine (Turing, 1937). This is a theoretical information processing model that employs the elementary gate processes described above. It can efficiently simulate any other device capable of performing an algorithmic process. Since the introduction of the Turing machine, physics has influenced computation in many ways.
The mathematical representation of the universe consists of sequences of symbols, rules and operators containing Gödel's undecidable propositions: information and its manipulation, also with Turing Machines. Classical information theory and mathematics, ideally independent from the medium used, can be interpreted realistically and objectively from their correspondence with quantum information, which is physical. Each representation of the universe and its evolution are, in any case, physical subsets of the universe, structured sets of observers and their complements in the universe made with spacetime events generated by local quantum measurements. Their description becomes a semantically closed structure without a global object-environment loss of decoherence as a von Neumann's universal constructor with a semantical abstract whose structure cannot be decided deterministically a priori from an internal observer. In a semantically closed structure, the realization of a specific event that writes the semantical abstract of the constructor is a problem of finding "which way" for the evolution of the universe as a choice of the constructor's state in a metastructure, like the many-world Everett scenario, from a specific result of any quantum measurement, corresponding to a Gödel undecidable proposition for an internal observer.
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.