We show how removing faith-based beliefs in current philosophies of classical and constructive mathematics admits formal, evidence-based, definitions of constructive mathematics; of a constructively well-defined logic of a formal mathematical language; and of a constructively well-defined model of such a language. -/- We argue that, from an evidence-based perspective, classical approaches which follow Hilbert's formal definitions of quantification can be labelled `theistic'; whilst constructive approaches based on Brouwer's philosophy of Intuitionism can be labelled `atheistic'. -/- We then adopt what may (...) be labelled a finitary, evidence-based, `agnostic' perspective and argue that Brouwerian atheism is merely a restricted perspective within the finitary agnostic perspective, whilst Hilbertian theism contradicts the finitary agnostic perspective. -/- We then consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary, evidence-based, definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways. -/- We show that the two definitions correspond to two distinctly different---not necessarily evidence-based but complementary---assignments of satisfaction and truth to the compound formulas of PA over N. -/- We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both the complementary interpretations; and conclude some unsuspected constructive consequences of such complementarity for the foundations of mathematics, logic, philosophy, and the physical sciences. -/- . (shrink)

Some have argued for a division of epistemic labor in which mathematicians supply truths and philosophers supply their necessity. We argue that this is wrong: mathematics is committed to its own necessity. Counterfactuals play a starring role.

I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s more, I (...) argue that these counterpossibles don’t just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models. (shrink)

This article is both a comment on Neyland’s ‘On organizing algorithms’ and a supplementary note to our ‘The concept of algorithm as an interpretative key of modern rationality’. In the first part we discuss the concepts of algorithm and recursive function from a different perspective from that of our previous article. Our cultural reference for these concepts is once again computability theory. We give additional arguments in support of the idea that a culture informed by an algorithmic logic has promoted (...) modern rationality both in science and in society. We stress again the importance of distinguishing between algorithms applied to quantifiable entities such as space, time and value and those applied to ontological entities such as human actions. In the second case, the algorithm is applied outside its domain of definition and leads to social disaggregation. (shrink)

A representation is a remnant of previous experience that allows that experience to affect later behavior. This paper develops a metatheoretical view of representation and applies it to issues concerning representation in animals. To describe a representational system one must specify the following: thedomainor range of situations in the represented world to which the system applies; thecontentor set of features encoded and preserved by the system; thecodeor transformational rules relating features of the representation to the corresponding features of the represented (...) world; themedium, or the representation's physical instantiation; and thedynamics, or how the system changes with time. In part because of the behaviorist assumption that the hypothetical, covert changes occurring in an organism during learning correspond to the overt physical changes that are observed, issues of representation in animal behavior have been largely ignored as irrelevant or misleading. However, it can be inferred that representations, acting as models of environmental regularities, operate at many levels of behavioral functioning, both cognitive and noncognitive. Objections to the use of this concept in explanations of animal behavior, based on the claim that it is indeterminate and on behaviorist considerations of parsimony, can be answered. Animal representations may be specialized in terms of tasks and species. Data from tasks involving spatial memory, delayed matching-to-sample, and sequence learning suggest some foundations for a general theory of animal representations. (shrink)

This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to (...) Turing’s notion of computability . Classical computability theory studies what functions on the natural numbers are computable and what mathematical problems are undecidable. Whilst a mathematical formalism of computability may perform a methodological function of evaluating computational theories of certain cognitive capacities, concrete computation in physical systems seems to be required for explaining cognition as an embodied phenomenon . There are many non-equivalent accounts of digital computation in physical systems. I examine only a handful of those in this paper: (1) Turing’s account ; (2) The triviality “account”; (3) Reconstructing Smith’s account of participatory computation ; (4) The Algorithm Execution account . My goal in this paper is twofold. First, it is to identify and clarify some of the underlying key requirements mandated by these accounts. I argue that these differing requirements justify a demand that one commits to a particular account when employing the notion of computation in regard to physical systems. Second, it is to argue that despite the informative role that mathematical formalisms of computability may play in cognitive science, they do not specify the relationship between abstract and concrete computation. (shrink)

The syllogistic figures and moods can be taken to be argument schemata as can the rules of the Stoic propositional logic. Sentence schemata have been used in axiomatizations of logic only since the landmark 1927 von Neumann paper [31]. Modern philosophers know the role of schemata in explications of the semantic conception of truth through Tarski’s 1933 Convention T [42]. Mathematical logicians recognize the role of schemata in first-order number theory where Peano’s second-order Induction Axiom is approximated by Herbrand’s Induction-Axiom (...) Schema [23]. Similarly, in first-order set theory, Zermelo’s second-order Separation Axiom is approximated by Fraenkel’s first-order Separation Schema [17]. In some of several closely related senses, a schema is a complex system having multiple components one of which is a template-text or scheme-template, a syntactic string composed of one or more “blanks” and also possibly significant words and/or symbols. In accordance with a side condition the template-text of a schema is used as a “template” to specify a multitude, often infinite, of linguistic expressions such as phrases, sentences, or argument-texts, called instances of the schema. The side condition is a second component. The collection of instances may but need not be regarded as a third component. The instances are almost always considered to come from a previously identified language (whether formal or natural), which is often considered to be another component. This article reviews the often-conflicting uses of the expressions ‘schema’ and ‘scheme’ in the literature of logic. It discusses the different definitions presupposed by those uses. And it examines the ontological and epistemic presuppositions circumvented or mooted by the use of schemata, as well as the ontological and epistemic presuppositions engendered by their use. In short, this paper is an introduction to the history and philosophy of schemata. (shrink)

This article presents Tarski's Address at the Princeton Bicentennial Conference on Problems of Mathematics, together with a separate summary. Two accounts of the discussion which followed are also included. The central topic of the Address and of the discussion is decision problems. The introductory note gives information about the Conference, about the background of the subjects discussed in the Address, and about subsequent developments to these subjects.

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism Lwx is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in Lwx forms a hereditarily undecidable theory in Lwx. These results generalize (...) similar theorems, due to Tarski, concerning relation algebras and the formalism Lx. (shrink)

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in (...) the limit if, after some finite point in the sequence, all the guesses are correct and the same. Functions, sets, and functionals which are decidable by such infinite algorithms will be calledlimiting recursive. These, together with classes of objects which can beidentified in the limit, are the subjects of this report.Without qualification,setwill mean set of numbers;functionwill mean number-theoretic function of 1 variable, possibly partial;functionalswill take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional,xwill invariably stand for a numerical variable;φfor a function variable;gfor a guess ;nfor the numerical variable which indexes the guesses, referred to as thetime. (shrink)

We consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary evidence-based definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways: (1) in terms of classical algorithmic verifiabilty; and (2) in terms of finitary algorithmic computability. We then show that the two definitions correspond to two distinctly different assignments of satisfaction and truth (...) to the compound formulas of PA over N---I_PA(N; SV ) and I_PA(N; SC). We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both I_PA(N; SV ) and I_PA(N; SC). We then show: (a) that if we assume the satisfaction and truth of the compound formulas of PA are always non-finitarily decidable under I_PA(N; SV ), then this assignment corresponds to the classical non-finitary putative standard interpretation I_PA(N; S) of PA over the domain N; and (b) that the satisfaction and truth of the compound formulas of PA are always finitarily decidable under the assignment I_PA(N; SC), from which we may finitarily conclude that PA is consistent. We further conclude that the appropriate inference to be drawn from Goedel's 1931 paper on undecidable arithmetical propositions is that we can define PA formulas which---under interpretation---are algorithmically verifiable as always true over N, but not algorithmically computable as always true over N. We conclude from this that Lucas' Goedelian argument is validated if the assignment I_PA(N; SV ) can be treated as circumscribing the ambit of human reasoning about `true' arithmetical propositions, and the assignment I_PA(N; SC) as circumscribing the ambit of mechanistic reasoning about `true' arithmetical propositions. (shrink)

In this paper we isolate a notion that we call “formalism freeness” from Gödel's 1946 Princeton Bicentennial Lecture, which asks for a transfer of the Turing analysis of computability to the cases of definability and provability. We suggest an implementation of Gödel's idea in the case of definability, via versions of the constructible hierarchy based on fragments of second order logic. We also trace the notion of formalism freeness in the very wide context of developments in mathematical logic in the (...) 20th century. (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)

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)

We investigate Turing's contributions to computability theory for real numbers and real functions presented in [22, 24, 26]. In particular, it is shown how two fundamental approaches to computable analysis, the so-called ‘Type-2 Theory of Effectivity' (TTE) and the ‘realRAM machine' model, have their foundations in Turing's work, in spite of the two incompatible notions of computability they involve. It is also shown, by contrast, how the modern conceptual tools provided by these two paradigms allow a systematic interpretation of Turing's (...) pioneering work in the subject. (shrink)

We study the measure independent character of Godel speed-up theorems. In particular, we strengthen Arbib's necessary condition for the occurrence of a Godel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Godel speed-ups and show that a theory τ 2 is a measure independent Godel speed-up of a theory τ 1 if and only if the set of undecidable sentences (...) of τ 1 which are provable in τ 2 is not recursively enumerable. (shrink)

A new reduction class is presented for the satisfiability problem for well-formed formulas of the first-order predicate calculus. The members of this class are closed prenex formulas of the form ∀ x∀ yC. The matrix C is in conjunctive normal form and has no disjuncts with more than three literals, in fact all but one conjunct is unary. Furthermore C contains but one predicate symbol, that being unary, and one function symbol which symbol is binary.

This paper concerns Alan Turing’s ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for (...) Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the “mathematical
objection” to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it
should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human
mathematicians presumably do. (shrink)