This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. I examine the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable propositions, (...) and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. I also develop a novel topic-sensitive truthmaker semantics for dynamic epistemic logic, and develop a novel dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for epistemic (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} are availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between my hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. I countenance a hyperintensional semantics for novel epistemic abstractionist modalities. I suggest, too, that observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. I invent a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. I provide a counter-example to epistemic closure for reductio proofs. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

Although Kurt Gödel does not figure prominently in the history of computabilty theory, he exerted a significant influence on some of the founders of the field, both through his published work and through personal interaction. In particular, Gödel’s 1931 paper on incompleteness and the methods developed therein were important for the early development of recursive function theory and the lambda calculus at the hands of Church, Kleene, and Rosser. Church and his students studied Gödel 1931, and Gödel taught a seminar (...) at Princeton in 1934. Seen in the historical context, Gödel was an important catalyst for the emergence of computability theory in the mid 1930s. (shrink)

This essay aims to provide a modal logic for rational intuition. Similarly to treatments of the property of knowledge in epistemic logic, I argue that rational intuition can be codified by a modal operator governed by the modal $\mu$-calculus. Via correspondence results between fixed point modal propositional logic and the bisimulation-invariant fragment of monadic second-order logic, a precise translation can then be provided between the notion of 'intuition-of', i.e., the cognitive phenomenal properties of thoughts, and the modal operators regimenting the (...) notion of 'intuition-that'. I argue that intuition-that can further be shown to entrain conceptual elucidation, by way of figuring as a dynamic-interpretational modality which induces the reinterpretation of both domains of quantification and the intensions and hyperintensions of mathematical concepts that are formalizable in monadic first- and second-order formal languages. Hyperintensionality is countenanced via a topic-sensitive epistemic two-dimensional truthmaker semantics. (shrink)

This essay examines the philosophical significance of Ω-logic in Zermelo-Fraenkel set theory with choice (ZFC). The dual isomorphism between algebra and coalgebra permits Boolean-valued algebraic models of ZFC to be interpreted as coalgebras. The modal profile of Ω-logical validity can then be countenanced within a coalgebraic logic, and Ω-logical validity can be defined via deterministic automata. I argue that the philosophical significance of the foregoing is two-fold. First, because the epistemic and modal profiles of Ω-logical validity correspond to those of (...) second-order logical consequence, Ω-logical validity is genuinely logical, and thus vindicates a neo-logicist conception of mathematical truth in the set-theoretic multiverse. Second, the foregoing provides a modal-computational account of the interpretation of mathematical vocabulary, adducing in favor of a realist conception of the cumulative hierarchy of sets. (shrink)

Gödel’s philosophical rationalism includes a program for “developing philosophy as an exact science.” Gödel believes that Husserl’s phenomenology is essential for the realization of this program. In this article, by analyzing Gödel’s philosophy of idealism, conceptual realism, and his concept of “abstract intuition,” based on clues from Gödel’s manuscripts, I try to investigate the reasons why Gödel is strongly interested in Husserl’s phenomenology and why his program for an exact philosophy is unfinished. One of the topics that has attracted much (...) attention recently is the development of Gödel’s philosophical thoughts and its connection with other philosophical ideas. For instance, some scholars are searching for the possible connections between Gödel’s philosophy and Husserl’s phenomenology and examining if there is any solid evidence of Husserl’s influence on Gödel from Gödel’s works (Tieszen, Bull Symbolic Logic 4(2):181–203, 1998; Huaser, Bull Symbolic Logic 12(4):529–588, 2006). Why is Gödel’ s interested in Husserl? How should this turn to Husserl be interpreted? Is it a dismissal of Leibnizian philosophy, or a different way to achieve similar goals? Way did Gödel turn specifically to Husserl’s transcendental idealism? (Van Atten and Kennedy, Bull Symbolic Logic 9(4):425–476, 2003) I believe, the reason is that Gödel has a valuable program for “developing philosophy as an exact science” and he believes that Husserl’s phenomenology is relevant to the realization of this program. So far there are no sufficient evidence to show that there is a direct inheritance relation between Gödel’s and Husserl’s thoughts. However, from the clues in Gödel’s idealistic philosophy, conceptual realism, and his concept of “abstract intuition,” we can perhaps explore some similarities between his thoughts and Husserl’s thoughts, and analyze the reason why Gödel is interested in Husserl’s phenomenology and why his program for an exact philosophy is unfinished. (shrink)

-/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical point of view, provability logic is interesting because (...) the concept of provability in a fixed theory of arithmetic has a unique and non-problematic meaning, other than concepts like necessity and knowledge studied in modal and epistemic logic. Furthermore, provability logic provides tools to study the notion of self-reference. (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)

This essay examines the philosophical significance of $\Omega$-logic in Zermelo-Fraenkel set theory with choice (ZFC). The categorical duality between coalgebra and algebra permits Boolean-valued algebraic models of ZFC to be interpreted as coalgebras. The hyperintensional profile of $\Omega$-logical validity can then be countenanced within a coalgebraic logic. I argue that the philosophical significance of the foregoing is two-fold. First, because the epistemic and modal and hyperintensional profiles of $\Omega$-logical validity correspond to those of second-order logical consequence, $\Omega$-logical validity is genuinely (...) logical. Second, the foregoing provides a hyperintensional account of the interpretation of mathematical and metamathematical vocabulary. (shrink)

We show that the name “Lucas-Penrose thesis” encompasses several different theses. All these theses refer to extremely vague concepts, and so are either practically meaningless, or obviously false. The arguments for the various theses, in turn, are based on confusions with regard to the meaning of these vague notions, and on unjustified hidden assumptions concerning them. All these observations are true also for all interesting versions of the much weaker thesis known as “Gö- del disjunction”. Our main conclusions are that (...) pure mathematical theorems cannot decide alone any question which is not purely mathematical, and that an argument that cannot be fully formalized cannot be taken as a mathematical proof. (shrink)

The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that (...) non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind. (shrink)

A debated issue in the mathematical foundations in at least the last two decades is whether one can plausibly argue for the merits of treating undecidable questions of mathematics, e.g., the Continuum Hypothesis, by relying on the existence of a plurality of set-theoretical universes except for a single one, i.e., the well-known set-theoretical universe V associated with the cumulative hierarchy of sets. The multiverse approach has some varying versions of the general concept of multiverse yet my intention is to primarily (...) address ontological multiversism as advocated, for instance, by Hamkins or Väätänen, precisely for the reason that they proclaim, to the one or the other extent, ontological preoccupations for the introduction of respective multiverse theories. Taking also into account Woodin’s and Steel’s multiverse versions, I take up an argumentation against multiversism, and in a certain sense against platonism in mathematical foundations, mainly on subjectively founded grounds, while keeping an eye on Clarke-Doane’s concern with Benacerraf’s challenge. I note that even though the paper is rather technically constructed in arguing against multiversism, the non-negligible philosophical part is influenced to a certain extent by a phenomenologically motivated view of the matter. (shrink)

The article deals with the question of in which sense the notion of explanation can be applied to Kurt Gödel’s philosophy of mathematics. Gödel, as a mathematical realist, claims that in mathematics we are dealing with facts that have an objective character. One of these facts is the solvability of all well-formulated mathematical problems—and this fact requires a clarification. The assumptions on which Gödel’s position is based are: metaphysical realism: there is a mathematical universe, it is objective and independent of (...) us; epistemological optimism: we are equipped with sufficient cognitive power to gain insight into the universe. Gödel’s concept of a solution to a mathematical problem is much broader than of a mathematical proof—it is rather about finding reliable axioms that lead to a solution of the problem. I analyse the problem presented in the article, taking as an example the continuum hypothesis. (shrink)

Artykuł dotyczy zagadnienia, w jakim sensie można stosować kategorię wyjaśnienia do interpretacji filozofii matematyki Kurta Gödla. Gödel – jako realista matematyczny – twierdzi bowiem, że w wypadku matematyki mamy do czynienia z niezależnymi od nas faktami. Jednym z owych faktów jest właśnie rozwiązywalność wszystkich dobrze postawionych problemów matematycznych – i ten fakt domaga się wyjaśnienia. Kluczem do zrozumienia stanowiska Gödla jest identyfikacja założeń, na których się opiera: metafizyczny realizm: istnieje uniwersum matematyczne, ma ono charakter obiektywny, niezależny od nas; optymizm epistemologiczny: (...) jesteśmy wyposażeni w wystarczająco dobre środki poznawcze, aby uzyskać wgląd w owo uniwersum. Pojęcie rozwiązania problemu matematycznego Gödel rozumie znacznie szerzej niż jako podanie matematycznego dowodu – chodzi raczej o znalezienie wiarogodnych aksjomatów, prowadzących do rozwiązania. Stawiany w artykule problem analizuję na przykładzie hipotezy kontinuum. (shrink)

In this paper, I explore an intriguing view of definable numbers proposed by a Cambridge mathematician Ernest Hobson, and his solution to the paradoxes of definability. Reflecting on König’s paradox and Richard’s paradox, Hobson argues that an unacceptable consequence of the paradoxes of definability is that there are numbers that are inherently incapable of finite definition. Contrast to other interpreters, Hobson analyses the problem of the paradoxes of definability lies in a dichotomy between finitely definable numbers and not finitely definable (...) numbers. To bypass this predicament, Hobson proposes a language dependent analysis of definable numbers, where the diagonal argument is employed as a means to generate more and more definable numbers. This paper examines Hobson’s work in its historical context, and articulates his argument in detail. It concludes with a remark on Hobson’s analysis of definability and Alan Turing’s analysis of computability. (shrink)

The abstract status of Kant's account of his ‘general logic’ is explained in comparison with Gödel's general definition of a formal logical system and reflections on ‘abstract’ (‘absolute’) concepts. Thereafter, an informal reconstruction of Kant's general logic is given from the aspect of the principles of contradiction, of sufficient reason, and of excluded middle. It is shown that Kant's composition of logic consists in a gradual strengthening of logical principles, starting from a weak principle of contradiction that tolerates a sort (...) of contradictions in predication, and then proceeding to the (constructive) principle of sufficient reason, and to a classical-like logic, which includes the principle of excluded middle. A first-order formalisation is applied to this reconstruction, which reveals implicit modalities in Kant's account of logic, and confirms the implementability of Kant's logic into a sound and complete formal system. (shrink)

This paper examines the philosophical significance of the consequence relation defined in the $\Omega$-logic for set-theoretic languages. I argue that, as with second-order logic, the hyperintensional profile of validity in $\Omega$-Logic enables the property to be epistemically tractable. Because of the duality between coalgebras and algebras, Boolean-valued models of set theory can be interpreted as coalgebras. In Section \textbf{2}, I demonstrate how the hyperintensional profile of $\Omega$-logical validity can be countenanced within a coalgebraic logic. Finally, in Section \textbf{3}, the philosophical (...) significance of the characterization of the hyperintensional profile of $\Omega$-logical validity for the philosophy of mathematics is examined. I argue (i) that $\Omega$-logical validity is genuinely logical, and (ii) that it provides a hyperintensional account of formal grasp of the concept of `set'. Section \textbf{4} provides concluding remarks. (shrink)

This paper proposes a possible reconstruction and philosophical-logical clarification of Gödel's idea of causality as the philosophical fundamental concept. The results are based on Gödel's published and non-published texts (including Max Phil notebooks), and are established on the ground of interconnections of Gödel's dispersed remarks on causality, as well as on the ground of his general philosophical views. The paper is logically informal but is connected with already achieved results in the formalization of a causal account of Gödel's onto-theological theory. (...) Gödel's main causal concepts are analysed (will, force, enjoyment, God, time and space, life, form, matter). Special attention is paid to a possible causal account of some of Gödel's logical concepts (assertion, privation, affirmation, negation, whole, part, general, particular, subject, predicate, necessary, possible, implication), as well as of logical antinomies. The problem of mechanical and non-mechanical procedures in the work with and on concepts is addressed in terms of Gödel's causal view. (shrink)

After a brief discussion of Kreisel’s notion of informal rigour and Myhill’s notion of absolute proof, Gödel’s analysis of the subject is presented. It is shown how Gödel avoids the notion of informal proof because such a use would contradict one of the senses of “formal” that Gödel wants to preserve. This Gödelian notion of “formal” is directly tied to his notion of absolute proof and to the question of the general applicability of concepts, in a way that overcomes both (...) Kreisel and Myhill’s conceptions. This paper aims to contribute to the present-day debate on informal and epistemic mathematics, focusing on what appears necessary for a better understanding of the issues at stake. (shrink)

Gödel has argued that we can cultivate the intuition or ‘perception’ of abstractconcepts in mathematics and logic. Gödel's ideas about the intuition of conceptsare not incidental to his later philosophical thinking but are related to many otherthemes in his work, and especially to his reflections on the incompleteness theorems.I describe how some of Gödel's claims about the intuition of abstract concepts are related to other themes in his philosophy of mathematics. In most of this paper, however,I focus on a central (...) question that has been raised in the literature on Gödel: what kind of account could be given of the intuition of abstract concepts? I sketch an answer to this question that uses some ideas of a philosopher to whom Gödel also turned in this connection: Edmund Husserl. The answer depends on how we understand the conscious directedness toward ‘objects’ and the meaning of the term ‘abstract’ in the context of a theory of the intentionality of cognition. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

Gödel’s philosophical rationalism includes a program for “developing philosophy as an exact science.” Gödel believes that Husserl’s phenomenology is essential for the realization of this program. In this article, by analyzing Gödel’s philosophy of idealism, conceptual realism, and his concept of “abstract intuition,” based on clues from Gödel’s manuscripts, I try to investigate the reasons why Gödel is strongly interested in Husserl’s phenomenology and why his program for an exact philosophy is unfinished. One of the topics that has attracted much (...) attention recently is the development of Gödel’s philosophical thoughts and its connection with other philosophical ideas. For instance, some scholars are searching for the possible connections between Gödel’s philosophy and Husserl’s phenomenology and examining if there is any solid evidence of Husserl’s influence on Gödel from Gödel’s works :181–203, 1998; Huaser, Bull Symbolic Logic 12:529–588, 2006). Why is Gödel’ s interested in Husserl? How should this turn to Husserl be interpreted? Is it a dismissal of Leibnizian philosophy, or a different way to achieve similar goals? Way did Gödel turn specifically to Husserl’s transcendental idealism? :425–476, 2003) I believe, the reason is that Gödel has a valuable program for “developing philosophy as an exact science” and he believes that Husserl’s phenomenology is relevant to the realization of this program. So far there are no sufficient evidence to show that there is a direct inheritance relation between Gödel’s and Husserl’s thoughts. However, from the clues in Gödel’s idealistic philosophy, conceptual realism, and his concept of “abstract intuition,” we can perhaps explore some similarities between his thoughts and Husserl’s thoughts, and analyze the reason why Gödel is interested in Husserl’s phenomenology and why his program for an exact philosophy is unfinished. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

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)

Although the case for the judgment-dependence of many other domains has been pored over, surprisingly little attention has been paid to mathematics and logic. This paper presents two dilemmas for a judgment-dependent account of these areas. First, the extensionality-substantiality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the substantiality condition (roughly: non-vacuous specification). Second, the extensionality-extremality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the extremality condition (...) (roughly: absence of independent explanation). The paper concludes with a moral concerning the judgment-dependence of a posteriori areas of discourse that emerges from consideration of these two a priori cases. (shrink)

The purpose of this article is to examine aspects of the development of the concept and theory of computability through the theory of recursive functions. Following a brief introduction, Section 2 is devoted to the presuppositions of computability. It focuses on certain concepts, beliefs and theorems necessary for a general property of computability to be formulated and developed into a mathematical theory. The following two sections concern situations in which the presuppositions were realized and the theory of computability was developed. (...) It is suggested in Section 3 that a central item was the problem of generalizing Gödel's incompleteness theorem. It is shown that this involved both the characterization of recursiveness and the attempt to clarify and formulate the notion of an effective process as it relates to the syntax of deductive systems. Section 4 concerns the decision problems which grew from the Hilbert program. Section 5 is devoted to the development of an informal' technique in the theory of computability often called ?argument by Church's thesis? (shrink)

We consider certain predicative classes with respect to their bearing on set theory, namely on its semantics, and on its ontological power. On the one hand, our predicative classes will turn out to be perfectly suited for establishing a nice hierarchy of metalanguages starting from the usual set theoretical language. On the other hand, these classes will be seen to be fairly inappropriate for the formulation of strong principles of infinity. The motivation for considering this very type of classes is (...) a reasonable philosophy of set theory. Familiarity is assumed only with basic concepts of both set theory and its philosophy. (shrink)

The present paper discusses a proposal which says,roughly and with several qualifications, that thecollection of mathematical truths is identical withthe set of theorems of ZFC. It is argued that thisproposal is not as easily dismissed as outright falseor philosophically incoherent as one might think. Some morals of this are drawn for the concept ofmathematical knowledge.

We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.

This paper challenges two orthodox theses: (a) that computational processes must be algorithmic; and (b) that all computed functions must be Turing-computable. Section 2 advances the claim that the works in computability theory, including Turing's analysis of the effective computable functions, do not substantiate the two theses. It is then shown (Section 3) that we can describe a system that computes a number-theoretic function which is not Turing-computable. The argument against the first thesis proceeds in two stages. It is first (...) shown (Section 4) that whether a process is algorithmic depends on the way we describe the process. It is then argued (Section 5) that systems compute even if their processes are not described as algorithmic. The paper concludes with a suggestion for a semantic approach to computation. (shrink)