Saul Kripke has proposed an argument to show that there is a serious problem with many computational accounts of physical systems and with functionalist theories in the philosophy of mind. The problem with computational accounts is roughly that they provide no noncircular way to maintain that any particular function with an infinite domain is realized by any physical system, and functionalism has the similar problem because of the character of the functional systems that are supposed to be realized by organisms. (...) This paper shows that the standard account of what it is for a physical system to compute a function can avoid Kripke's criticisms without being reduced to circularity; a very minor and natural elaboration of the standard account suffices to save both functionalist theories and computational accounts generally. (shrink)

Chaotic dynamics can be related to analog computation. A possibility of electronically implementing the chaos-driven contracting system in the target article is explored with an analog electronic circuit with inevitable noise from the viewpoint of analog computation with chaotic neurons.

It is fairly well-known that certain hard computational problems (that is, 'difficult' problems for a digital processor to solve) can in fact be solved much more easily with an analog machine. This raises questions about the true nature of the distinction between analog and digital computation (if such a distinction exists). I try to analyze the source of the observed difference in terms of (1) expanding parallelism and (2) more generally, infinite-state Turing machines. The issue of discreteness vs continuity will (...) also be touched upon, although it is not so important for analyzing these particular problems. (shrink)

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

The following paper presents a characterization of three distinctions fundamental to computationalism, viz., the distinction between analog and digital machines, representation and nonrepresentation-using systems, and direct and indirect perceptual processes. Each distinction is shown to rest on nothing more than the methodological principles which justify the explanatory framework of the special sciences.

It will always remain a remarkable phenomenon in the history of philosophy, that there was a time, when even mathematicians, who at the same time were philosophers, began to doubt, not of the accuracy of their geometrical propositions so far as they concerned space, but of their objective validity and the applicability of this concept itself, and of all its corollaries, to nature. They showed much concern whether a line in nature might not consist of physical points, and consequently that (...) true space in the object might consist of simple [discrete] parts, while the space which the geometer has in his mind [being continuous] cannot be such. (shrink)

In this paper, I argue for three claims. The first is that the difference between analog and digital representation lies in the format and not the medium of representation. The second is that whether a given system is analog or digital will sometimes depend on facts about the user of that system. The third is that the first two claims are implicit in Haugeland's (1998) account of the distinction.

The central claim of computationalism is generally taken to be that the brain is a computer, and that any computer implementing the appropriate program would ipso facto have a mind. In this paper I argue for the following propositions: (1) The central claim of computationalism is not about computers, a concept too imprecise for a scientific claim of this sort, but is about physical calculi (instantiated discrete formal systems). (2) In matters of formality, interpretability, and so forth, analog computation and (...) digital computation are not essentially different, and so arguments such as Searle''s hold or not as well for one as for the other. (3) Whether or not a biological system (such as the brain) is computational is a scientific matter of fact. (4) A substantive scientific question for cognitive science is whether cognition is better modeled by discrete representations or by continuous representations. (5) Cognitive science and AI need a theoretical construct that is the continuous analog of a calculus. The discussion of these propositions will illuminate several terminology traps, in which it''s all too easy to become ensnared. (shrink)

In this commentary on Harnad's "Grounding Symbols in the Analog World with Neural Nets: A Hybrid Model," the issues of symbol grounding and analog (continuous) computation are separated, it is argued that symbol graounding is as important an issue for analog cognitive models as for digital (discrete) models. The similarities and differences between continuous and discrete computation are discussed, as well as the grounding of continuous representations. A continuous analog of the Chinese Room is presented.

Representation is central to contemporary theorizing about the mind/brain. But the nature of representation--both in the mind/brain and more generally--is a source of ongoing controversy. One way of categorizing representational types is to distinguish between the analog and the digital: the received view is that analog representations vary smoothly, while digital representations vary in a step-wise manner. I argue that this characterization is inadequate to account for the ways in which representation is used in cognitive science; in its place, I (...) suggest an alternative taxonomy. I will defend and extend David Lewis's account of analog and digital representation, distinguishing analog from continuous representation, as well as digital from discrete representation. I will argue that the distinctions available in this four-fold account accord with representational features of theoretical interest in cognitive science more usefully than the received analog/digital dichotomy. (shrink)

Stevan Harnad correctly perceives a deep problem in computationalism, the hypothesis that cognition is computation, namely, that the symbols manipulated by a computational entity do not automatically mean anything. Perhaps, he proposes, transducers and neural nets will not have this problem. His analysis goes wrong from the start, because computationalism is not as rigid a set of theories as he thinks. Transducers and neural nets are just two kinds of computational system, among many, and any solution to the semantic problem (...) that works for them will work for most other computational systems. (shrink)

I offer an explication of the notion of computer, grounded in the practices of computability theorists and computer scientists. I begin by explaining what distinguishes computers from calculators. Then, I offer a systematic taxonomy of kinds of computer, including hard-wired versus programmable, general-purpose versus special-purpose, analog versus digital, and serial versus parallel, giving explicit criteria for each kind. My account is mechanistic: which class a system belongs in, and which functions are computable by which system, depends on the system's mechanistic (...) properties. Finally, I briefly illustrate how my account sheds light on some issues in the history and philosophy of computing as well as the philosophy of mind. (shrink)

``Neural computing'' is a research field based on perceiving the human brain as an information system. This system reads its input continuously via the different senses, encodes data into various biophysical variables such as membrane potentials or neural firing rates, stores information using different kinds of memories (e.g., short-term memory, long-term memory, associative memory), performs some operations called ``computation'', and outputs onto various channels, including motor control commands, decisions, thoughts, and feelings. We show a natural model of neural computing that (...) gives rise to hyper-computation. Rigorous mathematical analysis is applied, explicating our model's exact computational power and how it changes with the change of parameters. Our analog neural network allows for supra-Turing power while keeping track of computational constraints, and thus embeds a possible answer to the superiority of the biological intelligence within the framework of classical computer science. We further propose it as standard in the field of analog computation, functioning in a role similar to that of the universal Turing machine in digital computation. In particular an analog of the Church-Turing thesis of digital computation is stated where the neural network takes place of the Turing machine. (shrink)

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

The distinction between analog and digital representation is reexamined; it emerges that a more fundamental distinction is that between symbolic and analog simulation. Analog simulation is analyzed in terms of a (near) isomorphism of causal structures between a simulating and a simulated process. It is then argued that a core concept, naturalistic analog simulation, may play a role in a bottom-up theory of adaptive behavior which provides an alternative to representational analyses. The appendix discusses some formal conditions for naturalistic analog (...) simulation. (shrink)

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...) of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)

The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective (...) procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

To compute is to execute an algorithm. More precisely, to say that a device or organ computes is to say that there exists a modelling relationship of a certain kind between it and a formal specification of an algorithm and supporting architecture. The key issue is to delimit the phrase of a certain kind. I call this the problem of distinguishing between standard and nonstandard models of computation. The successful drawing of this distinction guards Turing's 1936 analysis of computation against (...) a difficulty that has persistently been raised against it, and undercuts various objections that have been made to the computational theory of mind. (shrink)

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

To build a true conscious robot requires that a robot’s “brain” be capable of supporting the phenomenal consciousness as human’s brain enjoys. Operational Architectonics framework through exploration of the temporal structure of information flow and inter-area interactions within the network of functional neuronal populations [by examining topographic sharp transition processes in the scalp electroencephalogram (EEG) on the millisecond scale] reveals and describes the EEG architecture which is analogous to the architecture of the phenomenal world. This suggests that the task of (...) creating the “machine” consciousness would require a machine implementation that can support the kind of hierarchical architecture found in EEG. (shrink)

The Construction of Personal Identities Online Content Type Journal Article Category Introduction Pages 1-3 DOI 10.1007/s11023-011-9254-y Authors Luciano Floridi, Department of Philosophy, University of Hertfordshire, de Havilland Campus, Hatfield, Hertfordshire, AL10 9AB UK Journal Minds and Machines Online ISSN 1572-8641 Print ISSN 0924-6495.

Cognitive science uses the notion of computational information processing to explain cognitive information processing. Some philosophers have argued that anything can be described as doing computational information processing; if so, it is a vacuous notion for explanatory purposes.An attempt is made to explicate the notions of cognitive information processing and computational information processing and to specify the relationship between them. It is demonstrated that the resulting notion of computational information processing can only be realized in a restrictive class of dynamical (...) systems called physical notational systems (after Goodman's theory of notationality), and that the systems generally appealed to by cognitive science-physical symbol systems-are indeed such systems. Furthermore, it turns out that other alternative conceptions of computational information processing, Fodor's (1975) Language of Thought and Cummins' (1989) Interpretational Semantics appeal to substantially the same restrictive class of systems. (shrink)

This paper presents some considerations about the relationship between languages and computer systems from a pragmatic, user-centered point of view.

I address whether neural networks perform computations in the sense of computability theory and computer science. I explicate and defend
the following theses. (1) Many neural networks compute—they perform computations. (2) Some neural networks compute in a classical way.
Ordinary digital computers, which are very large networks of logic gates, belong in this class of neural networks. (3) Other neural networks
compute in a non-classical way. (4) Yet other neural networks do not perform computations. Brains may well fall into this last class.

This paper offers an account of what it is for a physical system to be a computing mechanism—a system that performs computations. A computing mechanism is a mechanism whose function is to generate output strings from input strings and (possibly) internal states, in accordance with a general rule that applies to all relevant strings and depends on the input strings and (possibly) internal states for its application. This account is motivated by reasons endogenous to the philosophy of computing, namely, doing (...) justice to the practices of computer scientists and computability theorists. It is also an application of recent literature on mechanisms, because it assimilates computational explanation to mechanistic explanation. The account can be used to individuate computing mechanisms and the functions they compute and to taxonomize computing mechanisms based on their computing power. (shrink)

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

Because it is time-dependent, parallel computation is fundamentally different from sequential computation. Parallel programs are non-deterministic and are not effective procedures. Given the brain operates in parallel, this casts doubt on AI's attempt to make sequential computers intelligent.

What''s computation? The received answer is that computation is a computer at work, and a computer at work is that which can be modelled as a Turing machine at work. Unfortunately, as John Searle has recently argued, and as others have agreed, the received answer appears to imply that AI and Cog Sci are a royal waste of time. The argument here is alarmingly simple: AI and Cog Sci (of the Strong sort, anyway) are committed to the view that cognition (...) is computation (or brains are computers); butall processes are computations (orall physical things are computers); so AI and Cog Sci are positively silly.I refute this argument herein, in part by defining the locutions x is a computer and c is a computation in a way that blocks Searle''s argument but exploits the hard-to-deny link between What''s Computation? and the theory of computation. However, I also provide, at the end of this essay, an argument which, it seems to me, implies not that AI and Cog Sci are silly, but that they''re based on a form of computation that is well beneath human persons. (shrink)

David Chalmers has defended an account of what it is for a physical system to implement a computation. The account appeals to the idea of a “combinatorial-state automaton” or CSA. It is unclear whether Chalmers intends the CSA to be a computational model in the usual sense, or merely a convenient formalism into which instances of other models can be translated. I argue that the CSA is not a computational model in the usual sense because CSAs do not perspicuously represent (...) algorithms, are too powerful both in that they can perform any computation in a single step and in that without so far unspecified restrictions they can “compute” the uncomputable, and are too loosely related to physical implementations. (shrink)

While the sociality of software agents drives toward the definition of institutions for multi agent systems, their autonomy requires that such institutions are ruled by appropriate norm mechanisms. Computational institutions represent useful abstractions. In this paper we show how computational institutions can be built on top of the RoleX infrastructure, a role-based system with interesting features for our aim. We achieve a twofold goal: on the one hand, we give concreteness to the institution abstractions; on the other hand, we demonstrate (...) the flexibility of the RoleX infrastructure. (shrink)

Computation is central to the foundations of modern cognitive science, but its role is controversial. Questions about computation abound: What is it for a physical system to implement a computation? Is computation sufficient for thought? What is the role of computation in a theory of cognition? What is the relation between different sorts of computational theory, such as connectionism and symbolic computation? In this paper I develop a systematic framework that addresses all of these questions. Justifying the role of computation (...) requires analysis of implementation, the nexus between abstract computations and concrete physical systems. I give such an analysis, based on the idea that a system implements a computation if the causal structure of the system mirrors the formal structure of the computation. This account can be used to justify the central commitments of artificial intelligence and computational cognitive science: the thesis of computational sufficiency, which holds that the right kind of computational structure suffices for the possession of a mind, and the thesis of computational explanation, which holds that computation provides a general framework for the explanation of cognitive processes. The theses are consequences of the facts that (a) computation can specify general patterns of causal organization, and (b) mentality is an organizational invariant, rooted in such patterns. Along the way I answer various challenges to the computationalist position, such as those put forward by Searle. I close by advocating a kind of minimal computationalism, compatible with a very wide variety of empirical approaches to the mind. This allows computation to serve as a true foundation for cognitive science. (shrink)

Hilary Putnam has argued that computational functionalism cannot serve as a foundation for the study of the mind, as every ordinary open physical system implements every finite-state automaton. I argue that Putnam's argument fails, but that it points out the need for a better understanding of the bridge between the theory of computation and the theory of physical systems: the relation of implementation. It also raises questions about the class of automata that can serve as a basis for understanding the (...) mind. I develop an account of implementation, linked to an appropriate class of automata, such that the requirement that a system implement a given automaton places a very strong constraint on the system. This clears the way for computation to play a central role in the analysis of mind. (shrink)

To clarify the notion of computation and its role in cognitive science, we need an account of implementation, the nexus between abstract computations and physical systems. I provide such an account, based on the idea that a physical system implements a computation if the causal structure of the system mirrors the formal structure of the computation. The account is developed for the class of combinatorial-state automata, but is sufficiently general to cover all other discrete computational formalisms. The implementation relation is (...) non-vacuous, so that criticisms by Searle and others fail. This account of computation can be extended to justify the foundational role of computation in artificial intelligence and cognitive science. (shrink)

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

In the technical literature of computer science, the concept of an effective procedure is closely associated with the notion of an instruction that precisely specifies an action. Turing machine instructions are held up as providing paragons of instructions that "precisely describe" or "well define" the actions they prescribe. Numerical algorithms and computer programs are judged effective just insofar as they are thought to be translatable into Turing machine programs. Nontechnical procedures (e.g., recipes, methods) are summarily dismissed as ineffective on the (...) grounds that their instructions lack the requisite precision. But despite the pivotal role played by the notion of a precisely specified instruction in classifying procedures as effective and ineffective, little attention has been paid to the manner in which instructions "precisely specify" the actions they prescribe. It is the purpose of this paper to remedy this defect. The results are startling. The reputed exemplary precision of Turing machine instructions turns out to be a myth. Indeed, the most precise specifications of action are provided not by the procedures of theoretical computer science and mathematics (algorithms) but rather by the nontechnical procedures of everyday life. I close with a discussion of some of the rumifications of these conclusions for understanding and designing concrete computers and their programming languages. (shrink)

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...) of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

To compute is to execute an algorithm. More precisely, to say that a device or organ computes is to say that there exists a modelling relationship of a certain kind between it and a formal specification of an algorithm and supporting architecture. The key issue is to delimit the phrase of a certain kind. I call this the problem of distinguishing between standard and nonstandard models of computation. The successful drawing of this distinction guards Turing's 1936 analysis of computation against (...) a difficulty that has persistently been raised against it, and undercuts various objections that have been made to the computational theory of mind. (shrink)

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

Years ago, when I was an undergraduate math major at the University of Wyoming, I came across an interesting book in our library. It was a book of counterexamples t o propositions in real analysis (the mathematics of the real numbers). Mathematicians work more or less like the rest of us. They consider propositions. If one seems to them to be plausibly true, then they set about to prove it, to establish the proposition as a theorem. Instead o f setting (...) out to prove propositions, the psychologists, neuroscientists, and other empirical types among us, set out to show that a proposition is supported by the data, and that it is the best such proposition so supported. The philosophers among us, when they are not causing trouble by arguing that AI is a dead end or that cognitive science can get along without representations, work pretty much like the mathematicians: we set out to prove certain propositions true on the basis of logic, first principles, plausible assumptions, and others' data. But, back to the book of real analysis counterexamples. If some mathematician happened t o think that some proposition about continuity, say, was plausibly true, he or she would then set out to prove it. If the proposition was in fact not a theorem, then a lot of precious time would be wasted trying to prove it. Wouldn't it be great to have a book that listed plausibly true propositions that were in fact not true, and listed with each such proposition a counterexample to it? Of course it would. (shrink)

I critically examine some provocative arguments that John Searle presents in his book The Rediscovery of Mind to support the claim that the syntactic states of a classical computational system are "observer relative" or "mind dependent" or otherwise less than fully and objectively real. I begin by explaining how this claim differs from Searle's earlier and more well-known claim that the physical states of a machine, including the syntactic states, are insufficient to determine its semantics. In contrast, his more recent (...) claim concerns the syntax, in particular, whether a machine actually has symbols to underlie its semantics. I then present and respond to a number of arguments that Searle offers to support this claim, including whether machine symbols are observer relative because the assignment of syntax is arbitrary, or linked to universal realizability, or linked to the sub-personal interpretive acts of a homunculus, or linked to a person's consciousness. I conclude that a realist about the computational model need not be troubled by such arguments. Their key premises need further support. (shrink)

We critically discuss Cleland''s analysis of effective procedures as mundane effective procedures. She argues that Turing machines cannot carry out mundane procedures, since Turing machines are abstract entities and therefore cannot generate the causal processes that are generated by mundane procedures. We argue that if Turing machines cannot enter the physical world, then it is hard to see how Cleland''s mundane procedures can enter the world of numbers. Hence her arguments against versions of the Church-Turing thesis for number theoretic functions (...) miss the mark. (shrink)

Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as the work-horse of hypercomputation (Potgieter and Rosinger 2010: 853). But do they really compute beyond the Turing limit —e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the (...) term accelerating Turing machine is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical. (shrink)

A wide range of systems appear to perform computation: what common features do they share? I consider three examples, a digital computer, a neural network and an analogue route finding system based on soap-bubbles. The common feature of these systems is that they have autonomous dynamics — their states will change over time without additional external influence. We can take advantage of these dynamics if we understand them well enough to map a problem we want to solve onto them. Programming (...) consists of arranging the starting state of a system so that the effects of the system''s dynamics on some of its variables corresponds to the effects of the equations which describe the problem to be solved on their variables. The measured dynamics of a system, and hence the computation it may be performing, depend on the variables of the system we choose to attend to. Although we cannot determine which are the appropriate variables to measure in a system whose computation basis is unknown to us I go on to discuss how grammatical classifications of computational tasks and symbolic machine reconstruction techniques may allow us to rule out some measurements of a system from contributing to computation of particular tasks. Finally I suggest that these arguments and techniques imply that symbolic descriptions of the computation underlying cognition should be stochastic and that symbols in these descriptions may not be atomic but may have contents in alternative descriptions. (shrink)

Consciousness supervenes on activity; computation supervenes on structure. Because of this, some argue, conscious states cannot supervene on computational ones. If true, this would present serious difficulties for computationalist analyses of consciousness (or, indeed, of any domain with properties that supervene on actual activity). I argue that the computationalist can avoid the Superfluous Structure Problem (SSP) by moving to a dispositional theory of implementation. On a dispositional theory, the activity of computation depends entirely on changes in the intrinsic properties of (...) implementing material. As extraneous structure is not required for computation, a system can implement a program running on some but not all possible inputs. Dispositional computationalism thus permits episodes of computational activity that correspond to potential episodes of conscious awareness. The SSP cannot be motivated against this account, and so computationalism may be preserved. (shrink)

After briefly discussing the relevance of the notions computation and implementation for cognitive science, I summarize some of the problems that have been found in their most common interpretations. In particular, I argue that standard notions of computation together with a state-to-state correspondence view of implementation cannot overcome difficulties posed by Putnam's Realization Theorem and that, therefore, a different approach to implementation is required. The notion realization of a function, developed out of physical theories, is then introduced as a replacement (...) for the notional pair computation-implementation. After gradual refinement, taking practical constraints into account, this notion gives rise to the notion digital system which singles out physical systems that could be actually used, and possibly even built. (shrink)

There are different ways to present a Presidential Address to the APA; the one I have chosen is simply to report on work that I am doing right now, on work in progress. I am going to present some of my further explorations into the computational model of the mind.\**.

The evolutionary circuit design is an approach allowing engineers to realize computational devices. The evolved computational devices represent a distinctive class of devices that exhibits a specific combination of properties, not visible and studied in the scope of all computational devices up till now. Devices that belong to this class show the required behavior; however, in general, we do not understand how and why they perform the required computation. The reason is that the evolution can utilize, in addition to the (...) “understandable composition of elementary components”, material-dependent constructions and properties of environment (such as temperature, electromagnetic field etc.) and, furthermore, unknown physical behaviors to establish the required functionality. Therefore, nothing is known about the mapping between an abstract computational model and its physical implementation. The standard notion of computation and implementation developed in computer science as well as in cognitive science has become very problematic with the existence of evolved computational devices. According to the common understanding, the evolved devices cannot be classified as computing mechanisms. (shrink)

How can a virtual machine X be implemented in a physical machine Y? We know the answer as far as compilers, editors, theorem-provers, operating systems are concerned, at least insofar as we know how to produce these implemented virtual machines, and no mysteries are involved. This paper is about extrapolating from that knowledge to the implementation of minds in brains. By linking the philosopher's concept of supervenience to the engineer's concept of implementation, we can illuminate both. In particular, by showing (...) how virtual machines can be implemented in causally complete physical machines, and still have causal powers, we remove some philosophical problems about how mental processes can be real and can have real effects in the world even if the underlying physical implementation has no causal gaps. This requires a theory of ontological levels. (shrink)

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.

What''s computation? The received answer is that computation is a computer at work, and a computer at work is that which can be modelled as a Turing machine at work. Unfortunately, as John Searle has recently argued, and as others have agreed, the received answer appears to imply that AI and Cog Sci are a royal waste of time. The argument here is alarmingly simple: AI and Cog Sci (of the Strong sort, anyway) are committed to the view that cognition (...) is computation (or brains are computers); butall processes are computations (orall physical things are computers); so AI and Cog Sci are positively silly.I refute this argument herein, in part by defining the locutions x is a computer and c is a computation in a way that blocks Searle''s argument but exploits the hard-to-deny link between What''s Computation? and the theory of computation. However, I also provide, at the end of this essay, an argument which, it seems to me, implies not that AI and Cog Sci are silly, but that they''re based on a form of computation that is well beneath human persons. (shrink)

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.

The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also stored on the (...) tape. A small, fixed program that is 'hard-wired' into the head enables the head to read and execute the instructions of whatever program is on the tape. The machine's atomic operations are very simple—for example, 'move left one square', 'move right one square', 'identify the symbol currently beneath the head', 'write 1 on the square that is beneath the head', and 'write 0 on the square that is beneath the head'. Complexity of operation is achieved by the chaining together of large numbers of these simple atoms. Any universal Turing machine can be programmed to carry out any calculation that can be performed by a human mathematician working with paper and pencil in accordance with some algorithmic method. This is what is meant by calling these machines 'universal'. (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 recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

Hilary Putnam has argued that computational functionalism cannot serve as a foundation for the study of the mind, as every ordinary open physical system implements every finite-state automaton. I argue that Putnam's argument fails, but that it points out the need for a better understanding of the bridge between the theory of computation and the theory of physical systems: the relation of implementation. It also raises questions about the class of automata that can serve as a basis for understanding the (...) mind. I develop an account of implementation, linked to an appropriate class of automata, such that the requirement that a system implement a given automaton places a very strong constraint on the system. This clears the way for computation to play a central role in the analysis of mind. (shrink)

Some have suggested that there is no fact to the matter as to whether or not a particular physical system relaizes a particular computational description. This suggestion has been taken to imply that computational states are not real, and cannot, for example, provide a foundation for the cognitive sciences. In particular, Putnam has argued that every ordinary open physical system realizes every abstract finite automaton, implying that the fact that a particular computational characterization applies to a physical system does not (...) tell oneanything about the nature of that system. Putnam''s argument is scrutinized, and found inadequate because, among other things, it employs a notion of causation that is too weak. I argue that if one''s view of computation involves embeddedness (inputs and outputs) and full causality, one can avoid the universal realizability results. Therefore, the fact that a particular system realizes a particular automaton is not a vacuous one, and is often explanatory. Furthermore, I claim that computation would not necessarily be an explanatorily vacuous notion even if it were universally realizable. (shrink)

This paper investigates the relationship between reality and model, information and truth. It will argue that meaningful data need not be true in order to constitute information. Information to which truth-value cannot be ascribed, partially true information or even false information can lead to an interesting outcome such as technological innovation or scientific breakthrough. In the research process, during the transition between two theoretical frameworks, there is a dynamic mixture of old and new concepts in which truth is not well (...) defined. Instead of veridicity, correctness of a model and its appropriateness within a context are commonly required. Despite empirical models being in general only truthlike, they are nevertheless capable of producing results from which conclusions can be drawn and adequate decisions made. (shrink)

Knowledge generation can be naturalized by adopting computational model of cognition and evolutionary approach. In this framework knowledge is seen as a result of the structuring of input data (data → information → knowledge) by an interactive computational process going on in the agent during the adaptive interplay with the environment, which clearly presents developmental advantage by increasing agent’s ability to cope with the situation dynamics. This paper addresses the mechanism of knowledge generation, a process that may be modeled as (...) natural computation in order to be better understood and improved. (shrink)

Computers today are not only the calculation tools - they are directly (inter)acting in the physical world which itself may be conceived of as the universal computer (Zuse, Fredkin, Wolfram, Chaitin, Lloyd). In expanding its domains from abstract logical symbol manipulation to physical embedded and networked devices, computing goes beyond Church-Turing limit (Copeland, Siegelman, Burgin, Schachter). Computational processes are distributed, reactive, interactive, agent-based and concurrent. The main criterion of success of computation is not its termination, but the adequacy of its (...) response, its speed, generality and flexibility; adaptability, and tolerance to noise, error,faults, and damage. Interactive computing is a generalization of Turing computing, and it calls for new conceptualizations (Goldin, Wegner). In the info-computationalist framework, with computation seen as information processing, natural computation appears as the most suitable paradigm of computation and information semantics requires logical pluralism. (shrink)

Computing is changing the traditional field of Philosophy of Science in a very profound way. First as a methodological tool, computing makes possible ``experimental Philosophy'' which is able to provide practical tests for different philosophical ideas. At the same time the ideal object of investigation of the Philosophy of Science is changing. For a long period of time the ideal science was Physics (e.g., Popper, Carnap, Kuhn, and Chalmers). Now the focus is shifting to the field of Computing/Informatics. There are (...) many good reasons for this paradigm shift, one of those being a long standing need of a new meeting between the sciences and humanities, for which the new discipline of Computing/Informatics gives innumerable possibilities. Contrary to Physics, Computing/Informatics is very much human-centered. It brings a potential for a new Renaissance, where Science and Humanities, Arts and Engineering can reach a new synthesis, so very much needed in our intellectually split culture. This paper investigates contemporary trends and the relation between the Philosophy of Science and the Philosophy of Computing and Information, which is equivalent to the present relation between Philosophy of Science and Philosophy of Physics. (shrink)

We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) from a physical state to another, and (3) the size of the set of time--complexity functions that are compatible with the physical (...) resources required to reach a physical state from another. (shrink)

According to pancomputationalism, everything is a computing system. In this paper, I distinguish between different varieties of pancomputationalism. I find that although some varieties are more plausible than others, only the strongest variety is relevant to the philosophy of mind, but only the most trivial varieties are true. As a side effect of this exercise, I offer a clarified distinction between computational modelling and computational explanation.<br><br>.

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information‐processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I (...) also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game). *Received October 2008. †To contact the author, please write to: Department of Philosophy, University of Maryland, College Park, MD 20742; e‐mail: jbub@umd.edu. (shrink)

David Deutsch and others have suggested that the Many-Worlds Interpretation of quantum mechanics is the only interpretation capable of explaining the special efficiency quantum computers seem to enjoy over classical ones. I argue that this view is not tenable. Using a toy algorithm I show that the Many-Worlds Interpretation must crucially use the ontological status of the universal state vector to explain quantum computational efficiency, as opposed to the particular ontology of the MWI, that is, the computational histories of worlds. (...) As such, any other interpretation that treats the state vector as representing real ontological features of a system can explain quantum speedup too. ‡Thanks to Soazig Le Bihan for her critical comments on this paper. †To contact the author, please write to: Department of Philosophy, Liberal Arts 101, University of Montana, Missoula, MT 59812; e-mail: armond.duwell@umontana.edu. (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)

In quantum computing, where algorithms exist that can solve computational problems more efficiently than any known classical algorithms, the elimination of ...

Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics. The recent excitement in this lively and speculative domain of research was triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially "speed up" classical computation and factor large numbers into primes much more rapidly (at least in terms of the number of computational steps involved) than any known (...) classical algorithm. Shor's algorithm was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor's algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premiss that all known classical worst case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in tremendous attempts to tackle the technological difficulties that await the realization of such a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995, Ekert and Jozsa 1996, Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. (shrink)

I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

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 recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.

We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) from a physical state to another, and (3) the size of the set of time--complexity functions that are compatible with the physical (...) resources required to reach a physical state from another. (shrink)

_dualism_ (consciousness lies outside knowable science), _emergence_ (consciousness arises as a novel property from complex computational dynamics in the brain), and some form of _panpsychism_, _pan-protopsychism, or pan-experientialism_ (essential features or precursors of consciousness are fundamental components of reality which are accessed by brain processes). In addition to 1) the problem of subjective experience, other related enigmatic features of consciousness persist, defying technological and philosophical inroads. These include 2) the “binding problem”—how disparate brain activities give rise to a unified sense (...) of “self” or unified conscious content. Temporal synchrony—brain-wide coherence of neural membrane electrical activities—is often assumed to accomplish binding, but _what_ is being synchronized? What is being coherently bound? Another enigmatic feature is 3) the transition from pre-conscious processes to consciousness itself. Most neuroscientists agree that consciousness is the “tip of an iceberg”, that the vast majority of brain activities is. (shrink)

Proposals for quantum computation rely on superposed states implementing multiple computations simultaneously, in parallel, according to quantum linear superposition (e.g., Benioff, 1982; Feynman, 1986; Deutsch, 1985, Deutsch and Josza, 1992). In principle, quantum computation is capable of specific applications beyond the reach of classical computing (e.g., Shor, 1994). A number of technological systems aimed at realizing these proposals have been suggested and are being evaluated as possible substrates for quantum computers (e.g. trapped ions, electron spins, quantum dots, nuclear spins, etc., (...) see Table 1; Bennett, 1995; and Barenco, 1995). The main obstacle to realization of quantum computation is the problem of interfacing to the system (input, output) while also protecting the quantum state from environmental decoherence. If this problem can be overcome, then present day classical computers may evolve to quantum computers. (shrink)