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)

The paper presents an argument against a "metaphysical'* conception of logic according to which logic spells out a specific kind of mathematical structure that is somehow inherently related to our factual reasoning. In contrast, it is argued that it is always an empirical question as to whether a given mathematical structure really does captures a principle of reasoning. lMore generally, it is argued that it is not meaningful to replace an empirical investigation of a thing by an investigation of its (...) a priori analyzable structure without paying due attention to the question of whether it really is the structure of the thing in question.) It is proposed to elucidate the situation by distinguishing two essentially different realms with which our reason must deal: "the realm of the natural'*, constituted by the things of our empirical world, and "the realm of the formal'*, constituted by the structures that we use as "prisms'* to view, to make sense of, and to reconstruct the world. It is suggested that this vantage point may throw light on many foundational problems of logic. (shrink)

The paper surveys the currently available axiomatizations of common belief (CB) and common knowledge (CK) by means of modal propositional logics. (Throughout, knowledge- whether individual or common- is defined as true belief.) Section 1 introduces the formal method of axiomatization followed by epistemic logicians, especially the syntax-semantics distinction, and the notion of a soundness and completeness theorem. Section 2 explains the syntactical concepts, while briefly discussing their motivations. Two standard semantic constructions, Kripke structures and neighbourhood structures, are introduced in Sections (...) 3 and 4, respectively. It is recalled that Aumann's partitional model of CK is a particular case of a definition in terms of Kripke structures. The paper also restates the well-known fact that Kripke structures can be regarded as particular cases of neighbourhood structures. Section 3 reviews the soundness and completeness theorems proved w.r.t. the former structures by Fagin, Halpern, Moses and Vardi, as well as related results by Lismont. Section 4 reviews the corresponding theorems derived w.r.t. the latter structures by Lismont and Mongin. A general conclusion of the paper is that the axiomatization of CB does not require as strong systems of individual belief as was originally thought- only monotonicity has thusfar proved indispensable. Section 5 explains another consequence of general relevance: despite the "infinitary" nature of CB, the axiom systems of this paper admit of effective decision procedures, i.e., they are decidable in the logician's sense. (shrink)

On the basis of a wide range of historical examples various features of axioms are discussed in relation to their use in mathematical practice. A very general framework for this discussion is provided, and it is argued that axioms can play many roles in mathematics and that viewing them as self-evident truths does not do justice to the ways in which mathematicians employ axioms. Possible origins of axioms and criteria for choosing axioms are also examined. The distinctions introduced aim at (...) clarifying discussions in philosophy of mathematics and contributing towards a more refined view of mathematical practice. (shrink)

What are the objects of knowledge, belief, probability, apriority or analyticity? For at least some of these properties, it seems plausible that the objects are sentences, or sentence-like entities. However, results from mathematical logic indicate that sentential properties are subject to severe formal limitations. After surveying these results, I argue that they are more problematic than often assumed, that they can be avoided by taking the objects of the relevant property to be coarse-grained (“sets of worlds”) propositions, and that all (...) this has little to do with the choice between operators and predicates. (shrink)

This paper discusses the history of the confusion and controversies over whether the definition of consequence presented in the 11-page 1936 Tarski consequence-definition paper is based on a monistic fixed-universe framework?like Begriffsschrift and Principia Mathematica. Monistic fixed-universe frameworks, common in pre-WWII logic, keep the range of the individual variables fixed as the class of all individuals. The contrary alternative is that the definition is predicated on a pluralistic multiple-universe framework?like the 1931 Gödel incompleteness paper. A pluralistic multiple-universe framework recognizes multiple (...) universes of discourse serving as different ranges of the individual variables in different interpretations?as in post-WWII model theory. In the early 1960s, many logicians?mistakenly, as we show?held the ?contrary alternative? that Tarski 1936 had already adopted a Gödel-type, pluralistic, multiple-universe framework. We explain that Tarski had not yet shifted out of the monistic, Frege?Russell, fixed-universe paradigm. We further argue that between his Principia-influenced pre-WWII Warsaw period and his model-theoretic post-WWII Berkeley period, Tarski's philosophy underwent many other radical changes. (shrink)

Putnam famously attempted to use model theory to draw metaphysical conclusions. His Skolemisation argument sought to show metaphysical realists that their favourite theories have countable models. His permutation argument sought to show that they have permuted models. His constructivisation argument sought to show that any empirical evidence is compatible with the Axiom of Constructibility. Here, I examine the metamathematics of all three model-theoretic arguments, and I argue against Bays (2001, 2007) that Putnam is largely immune to metamathematical challenges.

Is it true that if zombies---creatures who are behaviorally indistinguishable from us, but no more conscious than a rock-are logically possible, the computational conception of mind is false? Are zombies logically possible? Are they physically possible? This paper is a careful, sustained argument for affirmative answers to these three questions.

Everything you always wanted to know about structural realism but were afraid to ask Content Type Journal Article Pages 227-276 DOI 10.1007/s13194-011-0025-7 Authors Roman Frigg, Department of Philosophy, Logic and Scientific Method, London School of Economics and Political Science, Houghton Street, London, WC2A 2AE UK Ioannis Votsis, Philosophisches Institut, Heinrich-Heine-Universität Düsseldorf, Universitätsstraße 1, Geb. 23.21/04.86, 40225 Düsseldorf, Germany Journal European Journal for Philosophy of Science Online ISSN 1879-4920 Print ISSN 1879-4912 Journal Volume Volume 1 Journal Issue Volume 1, Number 2.

p. cm. — (Zeuthen lecture book series) Includes bibliographical references (p. ) and index. ISBN 0-262-18187-8 (hardcover : alk. paper). — ISBN 0-262-68100-5 (pbk. : alk. paper) 1. Decision-making. 2. Economic man. 3. Game theory. 4. Rational expectations (Economic theory) I. Title. II. Series.

This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the ‘maximality thesis’), it discusses proposals for digital hypercomputing with Zeno-machines , i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either they are specified such (...) that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation. (shrink)

Bill Joy’s deep pessimism is now famous. Why the Future Doesn’t Need Us, his defense of that pessimism, has been read by, it seems, everyone—and many of these readers, apparently, have been converted to the dark side, or rather more accurately, to the future-is-dark side. Fortunately (for us; unfortunately for Joy), the defense, at least the part of it that pertains to AI and robotics, fails. Ours may be a dark future, but we cannot know that on the basis of (...) Joy’s reasoning. On the other hand, we ought to fear a good deal more than fear itself: we ought to fear not robots, but what some of us may do with robots. (shrink)

The philosophy of information (PI) is a new area of research with its own field of investigation and methodology. This article, based on the Herbert A. Simon Lecture of Computing and Philosophy I gave at Carnegie Mellon University in 2001, analyses the eighteen principal open problems in PI. Section 1 introduces the analysis by outlining Herbert Simon's approach to PI. Section 2 discusses some methodological considerations about what counts as a good philosophical problem. The discussion centers on Hilbert's famous analysis (...) of the central problems in mathematics. The rest of the article is devoted to the eighteen problems. These are organized into five sections: problems in the analysis of the concept of information, in semantics, in the study of intelligence, in the relation between information and nature, and in the investigation of values. (shrink)

This paper explains how mathematical computation can be constructed from weaker recursive patterns typical of natural languages. A thought experiment is used to describe the formalization of computational rules, or arithmetical axioms, using only orally-based natural language capabilities, and motivated by two accomplishments of ancient Indian mathematics and linguistics. One accomplishment is the expression of positional value using versified Sanskrit number words in addition to orthodox inscribed numerals. The second is Pāṇini’s invention, around the fifth century BCE, of a formal (...) grammar for spoken Sanskrit, expressed in oral verse extending ordinary Sanskrit, and using recursive methods rediscovered in the twentieth century. The Sanskrit positional number compounds and Pāṇini’s formal system are construed as linguistic grammaticalizations relying on tacit cognitive models of symbolic form. The thought experiment shows that universal computation can be constructed from natural language structure and skills, and shows why intentional capabilities needed for language use play a role in computation across all media. The evolution of writing and positional number systems in Mesopotamia is used to transfer the thought experiment of “oral arithmetic” to inscribed computation. The thought experiment and historical evidence combine to show how and why mathematical computation is a cognitive technology extending generic symbolic skills associated with language structure, usage, and change. (shrink)

Quantum Information Theory and the Foundations of Quantum Mechanics is a conceptual analysis of one of the most prominent and exciting new areas of physics, providing the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. -/- Beginning from a careful, revisionary, analysis of the concepts of information in the everyday and classical information-theory settings, Christopher G. Timpson argues for an ontologically deflationary account of the nature of quantum information. (...) Against what many have supposed, quantum information can be clearly defined (it is not a primitive or vague notion) but it is not part of the material contents of the world. Timpson's account sheds light on the nature of nonlocality and information flow in the presence of entanglement and, in particular, dissolves puzzles surrounding the remarkable process of quantum teleportation. In addition it permits a clear view of what the ontological and methodological lessons provided by quantum information theory are; lessons which bear on the gripping question of what role a concept like information has to play in fundamental physics. Topics discussed include the slogan 'Information is Physical', the prospects for an informational immaterialism (the view that information rather than matter might fundamentally constitute the world), and the status of the Church-Turing hypothesis in light of quantum computation. -/- With a clear grasp of the concept of information in hand, Timpson turns his attention to the pressing question of whether advances in quantum information theory pave the way for the resolution of the traditional conceptual problems of quantum mechanics: the deep problems which loom over measurement, nonlocality and the general nature of quantum ontology. He marks out a number of common pitfalls to be avoided before analysing in detail some concrete proposals, including the radical quantum Bayesian programme of Caves, Fuchs, and Schack. One central moral which is drawn is that, for all the interest that the quantum information-inspired approaches hold, no cheap resolutions to the traditional problems of quantum mechanics are to be had. (shrink)

It is now part and parcel of the official philosophical wisdom that models are essential to the acquisition and organisation of scientific knowledge. It is also generally accepted that most models represent their target systems in one way or another. But what does it mean for a model to represent its target system? I begin by introducing three conundrums that a theory of scientific representation has to come to terms with and then address the question of whether the semantic view (...) of theories, which is the currently most widely accepted account of theories and models, provides us with adequate answers to these questions. After having argued in some detail that it does not, I conclude by pointing out in what direction a tenable account of scientific representation might be sought. (shrink)

Philosophers of language have drawn on metamathematical results in varied ways. Extensionalist philosophers have been particularly impressed with two, not unrelated, facts: the existence, due to Frege/Tarski, of a certain sort of semantics, and the seeming absence of intensional contexts from mathematical discourse. The philosophical import of these facts is at best murky. Extensionalists will emphasize the success and clarity of the model theoretic semantics; others will emphasize the relative poverty of the mathematical idiom; still others will question the aptness (...) of the standard extensional semantics for mathematics. In this paper I investigate some implications of the Gödel Second Incompleteness Theorem for these positions. I argue that the realm of mathematics, proof theory in particular, has been a breeding ground for intensionality and that satisfactory intensional semantic theories are implicit in certain rigorous technical accounts. (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)

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines and more). There (...) are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds. (shrink)

I here investigate the sense in which diagonalization allows one to construct sentences that are self-referential. Truly self-referential sentences cannot be constructed in the standard language of arithmetic: There is a simple theory of truth that is intuitively inconsistent but is consistent with Peano arithmetic, as standardly formulated. True self-reference is possible only if we expand the language to include function-symbols for all primitive recursive functions. This language is therefore the natural setting for investigations of self-reference.

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of (...) the strength of the theory. I exhibit certain strong counterexamples and establish conclusively that the received view is false. Moreover, I show that the limiting constants provided by the theorem do not in any way reflect the power of formalized theories, but that the values of these constants are actually determined by the chosen coding of Turing machines, and are thus quite accidental. (shrink)

The paper presents an argument against a "metaphysical" conception of logic according to which logic spells out a specific kind of mathematical structure that is somehow inherently related to our factual reasoning. In contrast, it is argued that it is always an empirical question as to whether a given mathematical structure really does captures a principle of reasoning. (More generally, it is argued that it is not meaningful to replace an empirical investigation of a thing by an investigation of its (...) a priori analyzable structure without paying due attention to the question of whether it really is the structure of the thing in question.) It is proposed to elucidate the situation by distinguishing two essentially different realms with which our reason must deal: "the realm of the natural", constituted by the things of our empirical world, and "the realm of the formal", constituted by the structures that we use as "prisms" to view, to make sense of, and to reconstruct the world. It is suggested that this vantage point may throw light on many foundational problems of logic. (shrink)

The Turing Test is claimed by many to be a way to test for the presence, in computers, of such ``deep'' phenomena as thought and consciousness. Unfortunately, attempts to build computational systems able to pass TT have devolved into shallow symbol manipulation designed to, by hook or by crook, trick. The human creators of such systems know all too well that they have merely tried to fool those people who interact with their systems into believing that these systems really have (...) minds. And the problem is fundamental: the structure of the TT is such as to cultivate tricksters. A better test is one that insists on a certain restrictive epistemic relation between an artificial agent A, its output o, and the human architect H of A – a relation which, roughly speaking, obtains when H cannot account for how A produced o. We call this test the ``Lovelace Test'' in honor of Lady Lovelace, who believed that only when computers originate things should they be believed to have minds. (shrink)

It is a metaphysical orthodoxy that interesting non-symmetric relations cannot be reduced to symmetric ones. This orthodoxy is wrong. I show this by exploring the expressive power of symmetric theories, i.e. theories which use only symmetric predicates. Such theories are powerful enough to raise the possibility of Pythagrapheanism, i.e. the possibility that the world is just a vast, unlabelled, undirected graph.

There are two dominant approaches to quantification: the Fregean and the Tarskian. While the Tarskian approach is standard and familiar, deep conceptual objections have been pressed against its employment of variables as genuine syntactic and semantic units. Because they do not explicitly rely on variables, Fregean approaches are held to avoid these worries. The apparent result is that the Fregean can deliver something that the Tarskian is unable to, namely a compositional semantic treatment of quantification centered on truth and reference. (...) We argue that the Fregean approach faces the same choice: abandon compositionality or abandon the centrality of truth and reference to semantic theory. Indeed, we argue that developing a fully compositional semantics in the tradition of Frege leads to a typographic variant of the most radical of Tarskian views: variabilism, the view that names should be modeled as Tarskian variables. We conclude with the consequences of this result for Frege's distinction between sense and reference. (shrink)

This paper is concerned with counterfactual logic and its implications for the modal status of mathematical claims. It is most directly a response to an ambitious program by Yli-Vakkuri and Hawthorne (2018), who seek to establish that mathematics is committed to its own necessity. I claim that their argument fails to establish this result for two reasons. First, their assumptions force our hand on a controversial debate within counterfactual logic. In particular, they license counterfactual strengthening— the inference from ‘If A (...) were true then C would be true’ to ‘If A and B were true then C would be true’—which many reject. Second, the system they develop is provably equivalent to appending Deduction Theorem to a T modal logic. It is unsurprising that the combination of Deduction Theorem with T results in necessitation; indeed, it is precisely for this reason that many logicians reject Deduction Theorem in modal contexts. If Deduction Theorem is unacceptable for modal logic, it cannot be assumed to derive the necessity of mathematics. (shrink)

The goal of inquiry in this essay is to ascertain to what extent the Principle of Compositionality – the thesis that the meaning of a complex expression is determined by the meaning of its parts and its mode of composition – can be justifiably imposed as a constraint on semantic theories, and thereby provide information about what meanings are. Apart from the introduction and the concluding chapter the thesis is divided into five chapters addressing different questions pertaining to the overarching (...) goal of inquiry. Chapter Two is an attempt to determine whether the Principle of Compositionality is a trivial principle. It is argued that this is not the case in the context of providing the semantics of natural languages since it is an open question whether the best theories that respect available syntactic and semantic data are compositional. Chapter Three and Chapter Four ask whether there are reasons to think that the Principle of Compositionality is true. It is argued that the three most commonly cited reasons for thinking that correct semantic theories must be compositional – Linguistic Creativity, Productivity and Systematicity – in fact only give us reasons to think that the meaning of complex expressions depend on the meanings of their parts and their modes of composition, but not that the meaning of complex expressions depend ONLY on those factors. Chapter Five asks whether there are any reasons to think that the Principle of Compositionality is false. It is argued that all the phenomena that have been suggested entail non-compositionality are in fact compatible with some versions of compositionality. Even if this conclusion is reached in this chapter, the conclusion of the previous two chapters entails that we are not justified in imposing the Principle of Compositionality as an adequacy constraint on Semantic theories. Chapter Six explores the ways in which information about what meanings are can be derived by imposing constraints on semantic theories. It is argued that the distinction emphasized in Chapter Three and Chapter Four between depending on and depending ONLY on is of critical importance. It is demonstrated that the informative potential of the Principle of Compositionality goes far beyond that of the principle we are in fact justified in imposing on semantic theories. So not only is it the case that we cannot learn anything about meanings from the justified imposition of the Principle of Compositionality – since we cannot justifiably impose it as a constraint on semantic theories – what we could have learned from it had we been justified in imposing it is very different from what we can learn from the principle that we are justified in imposing. (shrink)

Tarski's indefinability theorem shows us that truth is not definable in arithmetic. The requirement to define truth for a language in a stronger language (if contradiction is to be avoided) lapses for particularly weak languages. A weaker language, however, is not necessary for that lapse. It also lapses for an adequately weak theory. It turns out that the set of G{\"o}del numbers of sentences true in arithmetic modulo $n$ is definable in arithmetic modulo $n$.

Artificial intelligence (AI) research enjoyed an initial period of enthusiasm in the 1970s and 80s. But this enthusiasm was tempered by a long interlude of frustration when genuinely useful AI applications failed to be forthcoming. Today, we are experiencing once again a period of enthusiasm, fired above all by the successes of the technology of deep neural networks or deep machine learning. In this paper we draw attention to what we take to be serious problems underlying current views of artificial (...) intelligence encouraged by these successes, especially in the domain of language processing. We then show an alternative approach to language-centric AI, in which we identify a role for philosophy. (shrink)

One of Tarski’s stated aims was to give an explication of the classical conception of truth—truth as ‘saying it how it is’. Many subsequent commentators have felt that he achieved this aim. Tarski’s core idea of defining truth via satisfaction has now found its way into standard logic textbooks. This paper looks at such textbook definitions of truth in a model for standard first-order languages and argues that they fail from the point of view of explication of the classical notion (...) of truth. The paper furthermore argues that a subtly different definition—also to be found in classic textbooks but much less prevalent than the kind of definition that proceeds via satisfaction—succeeds from this point of view. (shrink)

This is part two of a two-part paper in which we develop an axiomatic theory of the relation of partial ground. The main novelty of the paper is the of use of a binary ground predicate rather than an operator to formalize ground. In this part of the paper, we extend the base theory of the first part of the paper with hierarchically typed truth-predicates and principles about the interaction of partial ground and truth. We show that our theory is (...) a proof-theoretically conservative extension of the ramified theory of positive truth up to. (shrink)

According to some scholars, such as Rodych and Steiner, Wittgenstein objects to Gödel’s undecidability proof of his formula $$G$$, arguing that given a proof of $$G$$, one could relinquish the meta-mathematical interpretation of $$G$$ instead of relinquishing the assumption that Principia Mathematica is correct. Most scholars agree that such an objection, be it Wittgenstein’s or not, rests on an inadequate understanding of Gödel’s proof. In this paper, I argue that there is a possible reading of such an objection that is, (...) in fact, reasonable and related to Gödel’s proof. (shrink)

This paper concerns the relationship between transitivity of entailment, omega-inconsistency and nonstandard models of arithmetic. First, it provides a cut-free sequent calculus for non-transitive logic of truth STT based on Robinson Arithmetic and shows that this logic is omega-inconsistent. It then identifies the conditions in McGee for an omega-inconsistent logic as quantified standard deontic logic, presents a cut-free labelled sequent calculus for quantified standard deontic logic based on Robinson Arithmetic where the deontic modality is treated as a predicate, proves omega-inconsistency (...) and shows thus, pace Cobreros et al., that the result in McGee does not rely on transitivity. Finally, it also explains why the omega-inconsistent logics of truth in question do not require nonstandard models of arithmetic. (shrink)

This is part one of a two-part paper, in which we develop an axiomatic theory of the relation of partial ground. The main novelty of the paper is the of use of a binary ground predicate rather than an operator to formalize ground. This allows us to connect theories of partial ground with axiomatic theories of truth. In this part of the paper, we develop an axiomatization of the relation of partial ground over the truths of arithmetic and show that (...) the theory is a proof-theoretically conservative extension of the theory PT of positive truth. We construct models for the theory and draw some conclusions for the semantics of conceptualist ground. (shrink)

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)

The paper is concerned with Quine's substitutional account of logical truth. The critique of Quine's definition tends to focus on miscellaneous odds and ends, such as problems with identity. However, in an appendix to his influential article On Second Order Logic, George Boolos offered an ingenious argument that seems to diminish Quine's account of logical truth on a deeper level. In the article he shows that Quine's substitutional account of logical truth cannot be generalized properly to the general concept of (...) logical consequence. The purpose of this paper is threefold: first, to introduce the reader to the metamathematics of Quine's substitutional definition of logical truth; second, to make Boolos' result accessible to a broader audience by giving a detailed and self-contained presentation of his proof; and, finally, to discuss some of the possible implications and how a defender of the Quinean concepts might react to the challenge posed by Boolos' result. (shrink)

There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument (...) for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation. (shrink)

The kind of self-reference which Perlis characterizes as strong, as opposed to formal self-reference which he characterizes as weak, is actually already present in standard forms of formal self-reference. Even if formal self-reference is weak because it is delegated, there is no specific delegation of reference for self-referential sentences, and their ‘self’ part is strong enough. In particular, the structure of self-reference in Godel's sentence, with its application of a self-referential process to itself, provides a model of Perlis’ characterization of (...) a self. This structure can also be interpreted visually, in a way relevant to self and consciousness, namely as self-recognition in a mirror. (shrink)

A number of authors have argued that Peano Arithmetic supplemented with a logical validity predicate is inconsistent in much the same manner as is PA supplemented with an unrestricted truth predicate. In this paper I show that, on the contrary, there is no genuine paradox of logical validity—a completely general logical validity predicate can be coherently added to PA, and the resulting system is consistent. In addition, this observation lead to a number of novel, and important, insights into the nature (...) of logical validity itself. (shrink)

This is one of two papers about emergence, reduction and supervenience. It expounds these notions and analyses the general relations between them. The companion paper analyses the situation in physics, especially limiting relations between physical theories. I shall take emergence as behaviour that is novel and robust relative to some comparison class. I shall take reduction as deduction using appropriate auxiliary definitions. And I shall take supervenience as a weakening of reduction, viz. to allow infinitely long definitions. The overall claim (...) of this paper will be that emergence is logically independent both of reduction and of supervenience. In particular, one can have emergence with reduction, as well as without it; and emergence without supervenience, as well as with it. Of the subsidiary claims, the four main ones are: : I defend the traditional Nagelian conception of reduction ; : I deny that the multiple realizability argument causes trouble for reductions, or ``reductionism'' ; : I stress the collapse of supervenience into deduction via Beth's theorem ; : I adapt some examples already in the literature to show supervenience without emergence and vice versa. (shrink)

This paper describes Peirce's systems of logic diagrams, focusing on the so-called ''existential'' graphs, which are equivalent to the first-order predicate calculus. It analyses their implications for the nature of mental representations, particularly mental models with which they have many characteristics in common. The graphs are intended to be iconic, i.e., to have a structure analogous to the structure of what they represent. They have emergent logical consequences and a single graph can capture all the different ways in which a (...) possibility can occur. Mental models share these properties. But, as the graphs show, certain aspects of propositions cannot be represented in an iconic or visualisable way. They include negation, and the representation of possibilities qua possibilities, which both require representations that do not depend on a perceptual modality. Peirce took his graphs to reveal the fundamental operations of reasoning, and the paper concludes with an analysis of different hypotheses about these operations. (shrink)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

One of the most interesting and entertaining philosophical discussions of the last few decades is the discussion between Daniel Dennett and John Searle on the existence of intrinsic intentionality. Dennett denies the existence of phenomena with intrinsic intentionality. Searle, however, is convinced that some mental phenomena exhibit intrinsic intentionality. According to me, this discussion has been obscured by some serious misunderstandings with regard to the concept ‘intrinsic intentionality’. For instance, most philosophers fail to realize that it is possible that the (...) intentionality of a phenomenon is partly intrinsic and partly observer relative. Moreover, many philosophers are mixing up the concepts ‘original intentionality’ and ‘intrinsic intentionality’. In fact, there is, in the philosophical literature, no strict and unambiguous definition of the concept ‘intrinsic intentionality’. In this article, I will try to remedy this. I will also try to give strict and unambiguous definitions of the concepts ‘observer relative intentionality’, ‘original intentionality’, and ‘derived intentionality’. These definitions will be used for an examination of the intentionality of formal mathematical systems. In conclusion, I will make a comparison between the (intrinsic) intentionality of formal mathematical systems on the one hand, and the (intrinsic) intentionality of human beings on the other hand. (shrink)

The paper concerns interpretations of the paraconsistent logic LP which model theories properly containing all the sentences of first order arithmetic. The paper demonstrates the existence of such models and provides a complete taxonomy of the finite ones.