This paper engages the question ‘Does the consistency of a set of axioms entail the existence of a model in which they are satisfied?’ within the frame of the Frege-Hilbert controversy. The question is related historically to the formulation, proof and reception of Gödel’s Completeness Theorem. Tools from mathematical logic are then used to argue that there are precise senses in which Frege was correct to maintain that demonstrating consistency is as difficult as it can be, but also in which (...) Hilbert was correct to maintain that demonstrating existence given consistency is as easy as it can be. (shrink)

The existence of non-standard numbers in first-order arithmetics is a semantic obstacle for modelling our arithmetical skills. This article argues that so far there is no adequate approach to overcome such a semantic obstacle, because we can also find out, and deal with, non-standard elements in Turing machines.

Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ (...) problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

Alan Turing is often portrayed as a materialist in secondary literature. In the present article, I suggest that Turing was instead an idealist, inspired by Cambridge scholars, Arthur Eddington, Ernest Hobson, James Jeans and John McTaggart. I outline Turing’s developing thoughts and his legacy in the USA to date. Specifically, I contrast Turing’s two notions of computability (both from 1936) and distinguish between Turing’s “machine intelligence” in the UK and the more well-known “artificial intelligence” in the USA. According to my (...) proposed historical interpretation, Turing did not view computations in the real world to be exhaustively and deterministically characterized by his automatic machines from 1936. (shrink)

In the popular imagination, the relevance of Turing's theoretical ideas to people producing actual machines was significant and appreciated by everybody involved in computing from the moment he published his 1936 paper ‘On Computable Numbers’. Careful historians are aware that this popular conception is deeply misleading. We know from previous work by Campbell-Kelly, Aspray, Akera, Olley, Priestley, Daylight, Mounier-Kuhn, Haigh, and others that several computing pioneers, including Aiken, Eckert, Mauchly, and Zuse, did not depend on Turing's 1936 universal-machine concept. Furthermore, (...) it is not clear whether any substance in von Neumann's celebrated 1945 ‘First Draft Report on the EDVAC’ is influenced in any identifiable way by Turing's work. This raises the questions: When does Turing enter the field? Why did the Association for Computing Machinery honor Turing by associating his name to ACM's most prestigious award, the Turing Award? Previous authors have.. (shrink)

Alan Turing’s 1950 imitation game has been widely understood as a means for testing if an entity is intelligent. Following a series of papers by Diane Proudfoot, I offer a socio-technological interpretation of Turing’s paper and present an alternative way of understanding both the imitation game and Turing’s concept of intelligence. Turing, I claim, saw intelligence as a social concept, meaning that possession of intelligence is a property determined by society’s attitude toward the entity. He realized that as long as (...) human society held a prejudiced attitude toward machinery—seeing machines a priori as mindless objects—machines could not be said to be intelligent, by definition. He also realized, though, that if humans’ a priori, chauvinistic attitude toward machinery changed, the existence of intelligent machines would become logically possible. Turing thought that such a change would eventually occur: He believed that when scientists overcome the technological challenge of constructing sophisticated machines that could imitate human verbal behavior—i.e., do well in the imitation game—humans’ prejudiced attitude toward machinery will have altered in such a way that machines could be said to be intelligent. The imitation game, for Turing, was not an intelligence test, but a technological aspiration whose realization would likely involve a change in society’s attitude toward machines. (shrink)

A skeptical worry known as ‘the indeterminacy of computation’ animates much recent philosophical reflection on the computational identity of physical systems. On the one hand, computational explanation seems to require that physical computing systems fall under a single, unique computational description at a time. On the other, if a physical system falls under any computational description, it seems to fall under many simultaneously. Absent some principled reason to take just one of these descriptions in particular as relevant for computational explanation, (...) widespread failure of computational explanation would appear to follow. This paper advances a new solution to the indeterminacy of computation. Very roughly, I argue that the computational identity of a physical system is determinate relative to a contextually specified way of regarding that system computationally—known as a labelling scheme. When a system simultaneously implements multiple computations, it does so relative to different labelling schemes. But relative to a fixed labelling scheme, a physical system has a unique computational identity. I argue that this relativistic conception of computational identity vindicates computational explanation in the face of simultaneous implementation. (shrink)

This article advertises a new account of computational implementation. According to the resemblance account, implementation is a matter of resembling a computational architecture. The resemblance account departs from previous theories by denying that computational architectures are exhausted by their formal, mathematical features. Instead, they are taken to be permeated with causality, spatiotemporality, and other nonmathematical features. I argue that this approach comports well with computer scientific practice and offers a novel response to so-called triviality arguments.

In this paper we defend structural representations, more specifically neural structural representation. We are not alone in this, many are currently engaged in this endeavor. The direction we take, however, diverges from the main road, a road paved by the mathematical theory of measure that, in the 1970s, established homomorphism as the way to map empirical domains of things in the world to the codomain of numbers. By adopting the mind as codomain, this mapping became a boon for all those (...) convinced that a representation system should bear similarities with what was being represented, but struggled to find a precise account of what such similarities mean. The euforia was brief, however, and soon homomorphism revealed itself to be affected by serious weaknesses, the primary one being that it included systems embarrassingly alien to representations. We find that the defense attempts that have followed, adopt strategies that share a common format: valid structural representations come as “homomorphism plus X”, with various “X”, provided in descriptive format only. Our alternative direction stems from the observation of the overlooked departure from homomorphism as used in the theory of measure and its later use in mental representations. In the former case, the codomain or the realm of numbers, is the most suited for developing theorems detailing the existence and uniqueness of homomorphism for a wide range of empirical domains. In the latter case, the codomain is the realm of the mind, possibly more vague and more ill-defined than the empirical domain itself. The time is ripe for articulating the mapping between represented domains and the mind in formal terms, by exploiting what is currently known about coding mechanisms in the brain. We provide a sketch of a possible development in this direction, one that adopts the theory of neural population coding as codomain. We will show that our framework is not only not in disagreement with the “plus X” proposals, but can lead to natural derivation of several of the “X”. (shrink)

Work on how to axiomatize the subtheories of a first-order theory in which only a proper subset of their extra-logical vocabulary is being used led to a theorem on recursive axiomatizability and to an interpolation theorem for first-order logic. There were some fortuitous events and several logicians played a helpful role.

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Sumário Mostramos que, em virtude dos limites teóricos da computação, nem toda a ciência formulada com carácter preditivo pode ser simulada. Em particular, evidencia- se que a Fisica Clássica, nomeadamente a Físíca Newtoniana, padece deste mal, encerrando processos de Zenão.

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)

Alan Turing anticipated many areas of current research incomputer and cognitive science. This article outlines his contributionsto Artificial Intelligence, connectionism, hypercomputation, andArtificial Life, and also describes Turing's pioneering role in thedevelopment of electronic stored-program digital computers. It locatesthe origins of Artificial Intelligence in postwar Britain. It examinesthe intellectual connections between the work of Turing and ofWittgenstein in respect of their views on cognition, on machineintelligence, and on the relation between provability and truth. Wecriticise widespread and influential misunderstandings of theChurch–Turing thesis (...) and of the halting theorem. We also explore theidea of hypercomputation, outlining a number of notional machines thatcompute the uncomputable. (shrink)

Turing''s test has been much misunderstood. Recently unpublished material by Turing casts fresh light on his thinking and dispels a number of philosophical myths concerning the Turing test. Properly understood, the Turing test withstands objections that are popularly believed to be fatal.

In his PhD thesis (1938) Turing introduced what he described as 'a new kind of machine'. He called these 'O-machines'. The present paper employs Turing's concept against a number of currently fashionable positions in the philosophy of mind.

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)

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. (shrink)

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. (shrink)

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

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)

Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...) Turing’s analysis of computability; Turing’s Notational Thesis. (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.

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)

Turing’s paper on computable numbers has played its role in underpinning different perspectives on the world of information. On the one hand, it encourages a digital ontology, with a perceived flatness of computational structure comprehensively hosting causality at the physical level and beyond. On the other, it can give an insight into the way in which higher order information arises and leads to loss of computational control—while demonstrating how the control can be re-established, in special circumstances, via suitable type reductions. (...) We examine the classical computational framework more closely than is usual, drawing out lessons for the wider application of information–theoretical approaches to characterizing the real world. The problem which arises across a range of contexts is the characterizing of the balance of power between the complexity of informational structure and the means available to bring this information back into the computational fold. We proceed via appropriate mathematical modelling to a more coherent view of the computational structure of information, relevant to a wide spectrum of areas of investigation. (shrink)

A critical aspect of much human behaviour is the generation and regulation of sequential activities. Such behaviour is seen in both naturalistic settings such as routine action and language production and laboratory tasks such as serial recall and many reaction time experiments. There are a variety of computational mechanisms that may support the generation and regulation of sequential behaviours, ranging from those underlying Turing machines to those employed by recurrent connectionist networks. This paper surveys a range of such mechanisms, together (...) with a range of empirical phenomena related to human sequential behaviour. It is argued that the empirical phenomena pose difficulties for most sequencing mechanisms, but that converging evidence from behavioural flexibility, error data arising from when the system is stressed or when it is damaged following brain injury, and between-trial effects in reaction time tasks, point to a hybrid symbolic activation-based mechanism for the generation and regulation of sequential behaviour. Some implications of this view for the nature of mental computation are highlighted. (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 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)

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The (...) purpose of this survey is to convince the reader of our view. (shrink)

Despite his unreserved appreciation of Turing’s analysis for being a “precise and unquestionably adequate definition” of formal system or mechanical computability, Gödel nevertheless published a short note in 1972 claiming to have found a “philosophical error” in Turing’s argument with regard to the finite nature of mental states and memory. A natural question arises: how could Gödel enjoy the generality conferred on his results by Turing’s work, despite the error of its ways? Previous interpretative strategies by Feferman, Shagrir and others (...) have mainly tried to resolve the disparity by distinguishing different types of arguments in Turing and taking Gödel to approve only some of them. By a more integral examination of their ideas, especially Turing’s response to the “mathematical objection” based on Gödel’s incompleteness theorem and Gödel’s own conception of finite yet non-mechanical procedures, and taking some of the main ideas of current developments in machine learning into consideration, I will try to present a new explanation for the apparent disparity, arguing that there is no “error” on Turing’s side and the seemingly conflicting views held by Turing and Gödel should best be seen as complementary, keeping intuition and ingenuity together. (shrink)

Problem-solving software that is not-necessarily infallible is central to AI. Such software whose correctness and incorrectness properties are deducible by agents is an issue at the foundations of AI. The Comprehensibility Theorem, which appeared in a journal for specialists in formal mathematical logic, might provide a limitation concerning this issue and might be applicable to any agents, regardless of whether the agents are artificial or natural. The present article, aimed at researchers interested in the foundations of AI, addresses many questions (...) related to that theorem, including differences between it and results of Gödel and Turing that have sometimes played key roles in Minds and Machines articles. This study also suggests that—if one is willing to assume a thesis due to Donald Knuth—the Comprehensibility Theorem is the first mathematical theorem implying the impossibility of any AI agent or natural agent—including a not-necessarily infallible human agent—satisfying a rigorous and deductive interpretation of the self-comprehensibility challenge. Some have pointed out the difficulty of self-comprehensibility, even according to presumably a less rigorous interpretation. This includes Socrates, who considered it to be among the most important of intellectual tasks. Self-comprehensibility in some form might be essential for a kind of self-reflection useful for self-improvement that might enable some agents to increase their success. We use the methods of applied mathematics, rather than philosophy, although some topics considered could be of interest to philosophers. (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)

There are simple, purely syntactic axiomatic proof systems for both the logical truths and the logical falsehoods of propositional logic. However, to date no such system has been developed for the logical contingencies, that is, formulas that are both satisfiable and falsifiable. This paper formalizes the purely syntactic axiomatic proof systems for the logical contingencies and proves its soundness as well as completeness.

This paper argues that the ‘brain’ has become a frequently invoked and symptomatic source of metaphorical imagery in our current technologically mediated and dominated culture, through which the distinction between the human and the technological has been and continues to be negotiated, particularly in the context of the increasing ubiquity of electronic and digital technologies. This negotiation has thrown up three distinct, though interrelated, figures. One is the ‘Brain in a Vat’, in which the brain can connect to and even (...) operate solely through electronic technologies. Another is the ‘Electronic’ or, more archaically, ‘Giant Brain’, in which the brain’s functions can be reproduced and exceeded by electronic computing technology. A third is the ‘World’ or ‘Global Brain’, in which the connectivity enabled by information–communications technologies produces and fosters forms of distributed intelligence. This paper will trace the development of these figures and show how they have developed in lockstep throughout the two or three centuries of exponentially accelerating technological advance. (shrink)

Cognitive scientists use computational models to represent the results of their experimental work and to guide further research. Neither of these claims is particularly controversial, but the philosophical and evidentiary statuses of these models are hotly debated. To clarify the issues, I return to Newell and Simon’s 1972 exposition on the computational approach; they herald its ability to describe mental operations despite that the neuroscience of the time could not. Using work on visual imagery (cf. imagination) as a guide, I (...) examine the extent to which this holds true today. Does contemporary neuroscience contain mechanisms capable of describing experimental results in imagery? I argue that it does not, first by exploring foundational achievements in imagery research then by showing that their neural basis cannot be specified. Newell and Simon’s methodological position accordingly stands, even 50 years later. Computational — as opposed to physiological — descriptions must be retained to characterize and study mental phenomena, even as we learn high-level details of their implementation via brain data. (shrink)

The contrast between third- and first-personal accounts of the experiences of autistic persons has much to teach us about epistemic injustice and epistemic agency. This paper argues that bringing about greater epistemic justice for autistic people requires developing a relational account of epistemic agency. We begin by systematically identifying the many types of epistemic injustice autistic people face, specifically with regard to general assumptions regarding autistic people’s sociability or lack thereof, and by locating the source of these epistemic injustices in (...) neuronormativity and neurotypical ignorance. We then argue that this systematic identification pushes us to construe epistemic agency as resulting from a fundamentally relational and dynamic process between an individual, others around them, and their social, cultural, or institutional environment, rather than as a fixed and inherent property of individuals. Finally, we show how our relational account of epistemic agency allows us to introduce the novel concepts of epistemic disablement and epistemic enablement. We argue that these two concepts allow us to more accurately track the mechanisms that undermine or facilitate epistemic agency, and thereby to better understand how epistemic injustice arises and to design more effective interventions to foster greater epistemic justice for autistic people. (shrink)

Physicalism is the default position in science and in the philosophy of mind, but it should not be, I argue, because of two errors. By its epistemological error, physicalism gives physics priority over the evidence of first person experience. Only what I experience in first person is certain, so observation is prior to any theory. Physics itself is based on observation, avoiding the epistemological error, and then physics can progress, even changing its own ontology. However, physicalism imposes the ontology of (...) physics on every science, and in physics everything is causal. By its ontological error, physicalism tries to explain causally what is intentional. And it happens that causality and intentionality are mutually exclusive, showing that the ontology of physics is insufficient wherever intentions are present. This ontological insufficiency prevents that physicalism can repeat the success of physics with any science where intentions play a rôle, and thus it is blocking the advance of both the social sciences and the philosophy of mind. To overcome this obstacle, I propose to go back to the essentials: we should consider again the transcendental problem raised by Descartes and its solutions by Hume and Kant. On top of this subjectivist solution, we should take advantage of Darwin and Turing, and we should extend our ontology beyond causality to include intentionality, and here my proposal is problem solving. Then you could join our Post-Kantian subjectivism and say with me: The world is not a huge machine, as physicalism proposes, but an enigmatic problem. (shrink)