Online research in philosophy

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.

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.

I argue that neural activity, strictly speaking, is not computation. This is because computation, strictly speaking, is the processing of strings of symbols, and neuroscience shows that there are no neural strings of symbols. This has two consequences. On the one hand, the following widely held consequences of computationalism must either be abandoned or supported on grounds independent of computationalism: (i) that in principle we can capture what is functionally relevant to neural processes in terms of some formalism taken from computability theory (such as Turing Machines), (ii) that it is possible to design computer programs that are functionally equivalent to neural processes in the same sense in which it is possible to design computer programs that are functionally equivalent to each other, (iii) that the study of neural (or mental) computation is independent of the study of neural implementation, (iv) that the Church-Turing thesis applies to neural activity in the sense in which it applies to digital computers. On the other hand, we need to gradually reinterpret or replace computational theories in psychology in terms of theoretical constructs that can be realized by known neural processes, such as the spike trains of neuronal ensembles.Â.

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.

I argue that neural activity, strictly speaking, is not computation. This is because computation, strictly speaking, is the processing of strings of symbols, and neuroscience shows that there are no neural strings of symbols. This has two consequences. On the one hand, the following widely held consequences of computationalism must either be abandoned or supported on grounds independent of computationalism: (i) that in principle we can capture what is functionally relevant to neural processes in terms of some formalism taken from computability theory (such as Turing Machines), (ii) that it is possible to design computer programs that are functionally equivalent to neural processes in the same sense in which it is possible to design computer programs that are functionally equivalent to each other, (iii) that the study of neural (or mental) computation is independent of the study of neural implementation, (iv) that the Church-Turing thesis applies to neural activity in the sense in which it applies to digital computers. On the other hand, we need to gradually reinterpret or replace computational theories in psychology in terms of theoretical constructs that can be realized by known neural processes, such as the spike trains of neuronal ensembles.

The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. Specifically, communication with the outside world happens during the computation, not before or after it. This approach radically changes our understanding of what is computation and how it is modeled. The acceptance of interaction as a new paradigm is hindered by the Strong Church–Turing Thesis (SCT), the widespread belief that Turing Machines (TMs) capture all computation, so models of computation more expressive than TMs are impossible. In this paper, we show that SCT reinterprets the original Church–Turing Thesis (CTT) in a way that Turing never intended; its commonly assumed equivalence to the original is a myth. We identify and analyze the historical reasons for the widespread belief in SCT. Only by accepting that it is false can we begin to adopt interaction as an alternative paradigm of computation. We present Persistent Turing Machines (PTMs), that extend TMs to capture sequential interaction. PTMs allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of TMs and of the CTT. The paradigm shift to interaction provides an alternative understanding of the nature of computing that better reflects the services provided by today’s computing technology.

It is not widely realised that Turing was probably the first person to consider building computing machines out of simple, neuron-like elements connected together into networks in a largely random manner. Turing called his networks unorganised machines. By the application of what he described as appropriate interference, mimicking education an unorganised machine can be trained to perform any task that a Turing machine can carry out, provided the number of neurons is sufficient. Turing proposed simulating both the behaviour of the network and the training process by means of a computer program. We outline Turing's connectionist project of 1948.

According to the conventional wisdom, Turing (1950) said that computing machines can be intelligent. I don''t believe it. I think that what Turing really said was that computing machines –- computers limited to computing –- can only fake intelligence. If we want computers to become genuinelyintelligent, we will have to give them enough initiative (Turing, 1948, p. 21) to do more than compute. In this paper, I want to try to develop this idea. I want to explain how giving computers more ``initiative'''' can allow them to do more than compute. And I want to say why I believe (and believe that Turing believed) that they will have to go beyond computation before they can become genuinely intelligent.

A version of the Church-Turing Thesis states that every effectively realizable physical system can be defined by Turing Machines (‘Thesis P’); in this formulation the Thesis appears an empirical, more than a logico-mathematical, proposition. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. These models depend on infinite computation, explicitly or implicitly, and appear physically implausible; moreover, even if infinite computation were realizable, the Halting Problem would not be affected. Therefore, Thesis P is not essentially different from the standard Church-Turing Thesis. 1 Introduction 2 Computability and incomputability 3 The physical interpretation of the Church-Turing Thesis 4 Supertasks and infinite computation 5 Computation on non-well-founded domains 6 Analog computation 7 Quantum computation 8 Retrocausal computation 9 Conclusions.

It has been argued that neural networks and other forms of analog computation may transcend the limits of Turing-machine computation; proofs have been offered on both sides, subject to differing assumptions. In this article I argue that the important comparisons between the two models of computation are not so much mathematical as epistemological. The Turing-machine model makes assumptions about information representation and processing that are badly matched to the realities of natural computation (information representation and processing in or inspired by natural systems). This points to the need for new models of computation addressing issues orthogonal to those that have occupied the traditional theory of computation.