Cambridge University Press eBooks

Church’s Thesis, Turing’s Limits, and Deutsch’s Principle

Rossella Lupacchini

Published May 17, 2018• 2 citations

Abstract

In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.

DOI: 10.1017/9781316759745.004

Related papers

Quantum Speed-up of Computations

Itamar Pitowsky

Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system...Nophysically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of

Philosophy of ScienceSep 1, 200236 citations

Computation and Simulation

Liam Graham

Computation and simulation are key parts of the scientific project and are also central to understanding emergence. After a general discussion of the role of simulations in science, the chapter turns to the theory of computation, Turing machines and the Church-Turing principle. Limits to the scope of simulation would imply limits to science. Absolute limits would arise if some things are non-computable. Thinking about practical limits leads us to quantum computers, quantum simulations and an estimation of the computational capacity of the universe. The physical version of the Church-Turing principle states that if we can build a universal quantum computer we can simulate every physical system.

The frontiers collectionJan 1, 20250 citations

Quantum theory, the Church–Turing principle and the universal quantum computer

David Deutsch

Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.

Proceedings of the Royal Society of London A Mathematical and Physical SciencesJul 8, 19854,597 citations

Computable Functions, the Church-Turing Thesis and the Quantum Measurement Problem

R. Srikanth

It is possible in principle to construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolution, would contradict the Church-Turing thesis, which lies at the foundation of computer science. Elsewhere we have argued that the quantum measurement problem implies a finite, computational model of the measurement and evolution of quantum states. If correct, this approach helps to identify the key feature that can reconcile quantum mechanics with the Church-Turing thesis: finitude of the degree of fine-graining of Hilbert space. This suggests that the Church-Turing thesis constrains the physical universe and thereby highlights a surprising connection between purely logical and algorithmic considerations on the one hand and physical reality on the other.

arXiv:quant-ph/0402128Feb 18, 20045 citations

Measurability and Computability

Masanao Ozawa

The conceptual relation between the measurability of quantum mechanical observables and the computability of numerical functions is re-examined. A new formulation is given for the notion of measurability with finite precision in order to reconcile the conflict alleged by M. A. Nielsen [Phys. Rev. Lett. 79, 2915 (1997)] that the measurability of a certain observable contradicts the Church-Turing thesis. It is argued that any function computable by a quantum algorithm is a recursive function obeying the Church-Turing thesis, whereas any observable can be measured in principle.

arXiv:quant-ph/9809048Sep 16, 19988 citations

The Computational Status of Physics: A Computable Formulation of Quantum Theory

Mike Stannett

According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical systems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models' physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first principles, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as 'computing something' in the standard computational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.

arXiv:0805.1443May 10, 20081 citation