This paper explores the difference between Connectionist proposals for cognitive a r c h i t e c t u r e a n d t h e s o r t s o f m o d e l s t hat have traditionally been assum e d i n c o g n i t i v e s c i e n c e . W e c l a i m t h a t t h (...) e m a j o r d i s t i n c t i o n i s t h a t , w h i l e b o t h Connectionist and Classical architectures postulate representational mental states, the latter but not the former are committed to a symbol-level of representation, or to a ‘language of thought’: i.e., to representational states that have combinatorial syntactic and semantic structure. Several arguments for combinatorial structure in mental representations are then reviewed. These include arguments based on the ‘systematicity’ of mental representation: i.e., on the fact that cognitive capacities always exhibit certain symmetries, so that the ability to entertain a given thought implies the ability to entertain thoughts with semantically related contents. We claim that such arguments make a powerful case that mind/brain architecture is not Connectionist at the cognitive level. We then consider the possibility that Connectionism may provide an account of the neural (or ‘abstract neurological’) structures in which Classical cognitive architecture is implemented. We survey a n u m b e r o f t h e s t a n d a r d a r g u m e n t s t h a t h a v e b e e n o f f e r e d i n f a v o r o f Connectionism, and conclude that they are coherent only on this interpretation. (shrink)

A remarkable theorem by Clifton, Bub and Halvorson (2003) (CBH) characterizes quantum theory in terms of information--theoretic principles. According to Bub (2004, 2005) the philosophical significance of the theorem is that quantum theory should be regarded as a ``principle'' theory about (quantum) information rather than a ``constructive'' theory about the dynamics of quantum systems. Here we criticize Bub's principle approach arguing that if the mathematical formalism of quantum mechanics remains intact then there is no escape route from solving the measurement (...) problem by constructive theories. We further propose a (Wigner--type) thought experiment that we argue demonstrates that quantum mechanics on the information--theoretic approach is incomplete. (shrink)

We show that three fundamental information-theoretic constraints -- the impossibility of superluminal information transfer between two physical systems by performing measurements on one of them, the impossibility of broadcasting the information contained in an unknown physical state, and the impossibility of unconditionally secure bit commitment -- suffice to entail that the observables and state space of a physical theory are quantum-mechanical. We demonstrate the converse derivation in part, and consider the implications of alternative answers to a remaining open question about (...) nonlocality and bit commitment. (shrink)

Quantum computers are hypothetical quantum information processing (QIP) devices that allow one to store, manipulate, and extract information while harnessing quantum physics to solve various computational problems and do so putatively more efficiently than any known classical counterpart. Despite many ‘proofs of concept’ (Aharonov and Ben–Or 1996; Knill and Laflamme 1996; Knill et al. 1996; Knill et al. 1998) the key obstacle in realizing these powerful machines remains their scalability and susceptibility to noise: almost three decades after their conceptions, experimentalists (...) still struggle to maintain useful quantum coherence in QIP devices with more than a pair of qubits (e.g., Blatt and Wineland 2008). This slow progress has prompted debates on the feasibility of quantum computers, yet the quantum information community has dismissed the skepticism as “ideology” (Aaronson 2004), claiming that the obstacles are merely technological (Kaye et al. 2007, 240). In a recent paper (Hagar 2009) I’ve argued that such a skepticism with respect to the feasibility of quantum computers need not be deemed ideological at all, and that the aforementioned ‘proofs of concept’ are physically suspect. Using analogies from the foundations of classical statistical mechanics (SM), I’ve also argued that instead of active error correction, the appropriate framework for debating the feasibility of large–scale, fault–tolerant and computationally superior quantum computers should be the project of error avoidance: rather than trying to constantly ‘cool down’ the QIP device and prevent its thermalization, one should try to locate those regions in the device’s state space which are thermodynamically ‘abnormal’, i.e., those regions in the device’s state space which resist thermalization regardless of external noise. This paper is intended as a further contribution to the debate on the feasibility of large–scale, fault–tolerant and computationally superior quantum computers. Relying again on analogies from the foundations of classical SM, it suggests a skeptical conjecture and frames it in the ‘passive’, error avoidance, context.. (shrink)

This is an extensive review of recent work on the foundations of statistical mechanics.

Recent suggestions to supply quantum mechanics (QM) with realistic foundations by reformulating it in light of quantum information theory (QIT) are examined and are found wanting by pointing to a basic conceptual problem that QIT itself ignores, namely, the measurement problem. Since one cannot ignore the measurement problem and at the same time pretend to be a realist, as they stand, the suggestions to reformulate QM in light of QIT are nothing but instrumentalism in disguise.

This paper investigates what the source of time-asymmetry is in thermodynamics, and comments on the question whether a time-symmetric formulation of the Second Law is possible.

Wilfried Sieg and John Byrnes. AnModel for Parallel Computation: Gandy's Thesis.

We discuss a recent proposal by Albert (1994a; 1994b; 2000, ch. 7) to recover thermodynamics on a purely dynamical basis, using the quantum theory of the collapse of the wave function by Ghirardi, Rimini, and Weber (1986). We propose an alternative way to explain thermodynamics within no-collapse interpretations of quantum mechanics. Our approach relies on the standard quantum mechanical models of environmental decoherence of open systems (e.g., Joos and Zeh 1985; Zurek and Paz 1994). This paper presents the two approaches (...) and discusses their advantages. The problems faced by both approaches will be discussed in a sequel (Hemmo and Shenker 2003). (shrink)

A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously enough-and this is (...) the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

Among the alternatives of non-relativistic quantum mechanics (NRQM) there are those that give different predictions than quantum mechanics in yet-untested circumstances, while remaining compatible with current empirical findings. In order to test these predictions, one must isolate one’s system from environmental induced decoherence, which, on the standard view of NRQM, is the dynamical mechanism that is responsible for the ‘apparent’ collapse in open quantum systems. But while recent advances in condensed-matter physics may lead in the near future to experimental setups (...) that will allow one to test the two hypotheses, namely genuine collapse vs. decoherence, hence make progress toward a solution to the quantum measurement problem, those philosophers and physicists who are advocating an information-theoretic approach to the foundations of quantum mechanics are still unwilling to acknowledge the empirical character of the issue at stake. Here I argue that in doing so they are displaying an unwarranted double standard. r 2007 Elsevier Ltd. All rights reserved. (shrink)

The strange story of the von Neumann impossibility proof is recalled, and the even stranger story of later impossibility proofs, and how the impossible was done by de Broglie and Bohm. Morals are drawn.

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.

1. The Physical Church-Turing Thesis. Physicists often interpret the 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 . . . (...) No physically 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. (shrink)

The intuition guiding the de…nition of computation has shifted over time, a process that is re‡ected in the changing formulations of the Church-Turing thesis. The theory of computation began with logic and gradually moved to the capacity of …nite automata. Consequently, modern computer models rely on general physical principles, with quantum computers representing the extreme case. The paper discusses this development, and the challenges to the Church-Turing thesis in its physical form, in particular, Kieu’s quantum computer and relativistic hyper-computation. Finally, (...) the robustness of the boundary between polynomial and exponential time complexity is considered in connection with quantum computers and quantum information theory. (shrink)