Putnam Mapping

Piccinini:
"The mapping account says, roughly, that a computing system is a concrete system such that there is a computational description that maps onto a physical description of the system. If any mapping is acceptable, it can be shown that almost every physical system implements every computation (Putnam 1988, Searle 1992). This trivialization result can be avoided by putting appropriate restrictions on acceptable mappings; for instance, legitimate mappings must respect causal relations between physical states (Chrisley 1995, Chalmers 1996, Copeland 1996, Scheutz 2001).

Still, there remain mappings between (many) computational descriptions and any physical system. Under the mapping account, everything performs at least some computations. This still strikes some as a trivialization of computationalism. Furthermore, it doesn"t do justice to computer science, where only relatively few systems count as performing computations. Those who want to restrict the notion of computation further have to look beyond the mapping account of computation."

"Putnam's proposal, and its historical importance, was analyzed in detail in Piccinini forthcoming b. According to Putnam (1960, 1967,1988), a system is a computing mechanism if and only if there is a mapping between a computational description and a physical description of the system. By computational description, Putnam means a formal description of the kind used in computability theory, such as a Turing Machine or a finite state automaton. Putnam puts no constraints on how to find the mapping between the computational and the physical description, allowing any computationally identified state to map onto any physically identified state. It is well known that Putnam's account entails that most physical systems implement most computations. This consequence of Putnam's proposal has been explicitly derived by Putnam (1988, pp. 95-96, 121-125) and Searle (1992, chap. 9)."

Quantum Computing and the Church-Turing Thesis

Another interesting article.

The Turing machine model seems to capture the entire concept of computability, according to the following thesis[62]:

Church Turing Thesis: A Turing machine can compute any function computable by a reasonable physical device.

What does “reasonable physical device” mean? This thesis is a physical statement, and as such it cannot be proven. But one knows a physically unreasonable device when one sees it. Up till now there are no candidates for counterexamples to this thesis (but see Ref. [103]). All physical systems, (including quantum systems), seem to have a simulation by a Turing Machine.

Quantum Computing: Introduction

More on the relationship between quantum computing and classical computing. An interesting read.

Another thing which can be expressed in many different ways is information. For example, the two statements ``the quantum computer is very interesting'' and ``l'ordinateur quantique est tres interessant'' have something in common, although they share no words. The thing they have in common is their information content. Essentially the same information could be expressed in many other ways, for example by substituting numbers for letters in a scheme such as a -> 97, b -> 98, c -> 99 and so on, in which case the english version of the above statement becomes 116 104 101 32 113 117 97 110 116 117 109... . It is very significant that information can be expressed in different ways without losing its essential nature, since this leads to the possibility of the automatic manipulation of information: a machine need only be able to manipulate quite simple things like integers in order to do surprisingly powerful information processing, from document preparation to differential calculus, even to translating between human languages. We are familiar with this now, because of the ubiquitous computer, but even fifty years ago such a widespread significance of automated information processing was not forseen.

Quantum Computing vs. Turing Machines

SEP on Quantum Computing:

Although the original Church-Turing thesis involved the abstract mathematical notion of computability, physicists as well as computer scientists often interpret it as saying something about the scope and limitations of physical computing machines. For example, Wolfram (1985) claims that any physical system can be simulated (to any degree of approximation) by a universal Turing machine, and that complexity bounds on Turing machine simulations have physical significance. For example, if the computation of the minimum energy of some system of n particles requires at least an exponentially increasing number of steps in n, then the actual relaxation of this system to its minimum energy state will also take an exponential time. Aharonov (1998) strengthens this thesis (in the context of showing its putative incompatibility with quantum mechanics) when she says that a probabilistic Turing machine can simulate any reasonable physical device at polynomial cost. Further examples for this thesis can be found in Copeland (1996).

AND:

Theoretical as it may seem, the question "what is quantum in quantum computing?" has an enormous practical consequence. One of the embarrassments of quantum computing is the fact that, so far, only one algorithm has been discovered, namely Shor's, for which a quantum computer is significantly faster than any known classical one. It is almost certain that one of the reasons for this scarcity of quantum algorithms is related to the lack of our understanding of what makes a quantum computer quantum (see also Preskill 1998 and Shor 2004). As an ultimate answer to this question one would like to have something similar to Bell's (1964) famous theorem, i.e., a succinct crispy statement of the fundamental difference between quantum and classical systems, encapsulated in the non-commutative character of observables. Quantum computers, unfortunately, do not seem to allow such simple characterization. Observables—in the quantum circuit model there are only two, the preparation of the initial state and the observation of the final state, in the same basis, and of the same variable, at the end of the computation—are not as important here as in Bell's case since any measurement commutes with itself. The non-commutativity in quantum computing lies much deeper, and it is still unclear how to cash it into useful currency. Quantum computing skeptics (Levin 2003) happily capitalize on this puzzle: If no one knows why quantum computers are superior to classical ones, how can we be sure that they are, indeed, superior?