A number of examples have been given of physical systems (both classical and quantum mechanical) which when provided with a (continuously variable) computable input will give a non-computable output. It has been suggested that these systems might allow one to design analogue machines which would calculate the values of some number-theoretic non-computable function. Analysis of the examples show that the suggestion is wrong. In Section 4 I claim that given a reasonable definition of analogue machine it will always be wrong. (...) The claim is to be read not so much as a dogmatic assertion, but rather as a challenge. -/- In Sections 1 and 2 I discuss analogue machines, and lay down some conditions which I believe they must satisfy. In Section I discuss the particular forms which a paradigm undecidable problem (or non-computable function) may take. In Sections 5 and 6 I justify any claim for two particular examples lying within the range of classical physics, and in Section 7 I justify it for two (closely connected) examples from quantum mechanics, and discuss, very briefly, other possible quantum mechanical situations. Section 8 contains various remarks and comments. In Section 9 I consider the suggestion made by Penrose that a (future) theory of quantum gravity may predict non-locally-determined, and perhaps non-computable patterns of growth for microsopic structures. My conclusion is that such a theory will have to have non-computability built into it. (shrink)

Las máquinas aceleradas de Turing (ATMs) son dispositivos capaces de ejecutar súper-tareas. Sin embargo, el simple ejercicio de definirlas ha generado varias paradojas. En el presente artículo se definirán las nociones de súper-tarea y ATM de manera exhaustiva y se aclarará qué debe entenderse en un contexto lógico-formal cuando se pregunta por la existencia de un objeto. A partir de la distinción entre posibilidades lógicas y físicas se disolverán las paradojas y se concluirá que las ATMs son posibles y existen (...) como objetos abstractos. (shrink)

Evaluative studies of inductive inferences have been pursued extensively with mathematical rigor in many disciplines, such as statistics, econometrics, computer science, and formal epistemology. Attempts have been made in those disciplines to justify many different kinds of inductive inferences, to varying extents. But somehow those disciplines have said almost nothing to justify a most familiar kind of induction, an example of which is this: “We’ve seen this many ravens and they all are black, so all ravens are black.” This is (...) enumerative induction in itsfullstrength. For it does not settle with a weaker conclusion (such as “the ravens observed in the future will all be black”); nor does it proceed with any additional premise (such as the statistical IID assumption). The goal of this paper is to take some initial steps toward a justification for the full version of enumerative induction, against counterinduction, and against the skeptical policy. The idea is to explore various epistemic ideals, mathematically defined as different modes of convergence to the truth, and look for one that is weak enough to be achievable and strong enough to justify a norm that governs both the long run and the short run. So the proposal is learning-theoretic in essence, but a Bayesian version is developed as well. (shrink)

In the first section, five major attempts to solve the problem of induction and their failures are discussed. In the second section, an account of meta-induction is introduced. It offers a novel solution to the problem of induction, based on mathematical theorems about the predictive optimality of attractivity-weighted meta-induction. In the third section, how the a priori justification of meta-induction provides a non-circular a posteriori justification of object-induction, based on its superior track record, is explained. In the fourth section, four (...) important extensions and refinements of the method of meta-induction are presented. The final section, summarizes the major impacts of the program of meta-induction for epistemology, the philosophy of science and cognitive science. (shrink)

From the initial analysis of John Morris in 1976 about if computers can lie, I have presented my own treatment of the problem using what can be called a computational lying procedure. One that uses two Turing Machines. From there, I have argued that such a procedure cannot be implemented in a Turing Machine alone. A fundamental difficulty arises, concerning the computational representation of the self-knowledge a machine should have about the fact that it is lying. Contrary to Morris’ claim, (...) I have thus suggested that computers – as far as they are Turing Machines – cannot lie. Consequently, I have claimed that moral agency attribution to a robot or any other automated AI system, cannot be made, strictly grounded on imitating behaviors. Self-awareness as an ontological grounding for moral attribution must be evoked. This can pose a recognition problem from our part, should the sentient system be the only agent capable of acknowledging its own sentience. (shrink)

The most widespread models of rational reasoners (the model based on modal epistemic logic and the model based on probability theory) exhibit the problem of logical omniscience. The most common strategy for avoiding this problem is to interpret the models as describing the explicit beliefs of an ideal reasoner, but only the implicit beliefs of a real reasoner. I argue that this strategy faces serious normative issues. In this paper, I present the more fundamental problem of logical omnipotence, which highlights (...) the normative content of the problem of logical omniscience. I introduce two developments of the notion of implicit belief (accessible and stable belief ) and use them in two versions of the most common strategy applied to the problem of logical omnipotence. (shrink)

Putnam’s most famous contribution to mathematical logic was his role in investigating Hilbert’s Tenth Problem; Putnam is the ‘P’ in the MRDP Theorem. This volume, though, focusses mostly on Putnam’s work on the philosophy of logic and mathematics. It is a somewhat bumpy ride. Of the twelve papers, two scarcely mention Putnam. Three others focus primarily on Putnam’s ‘Mathematics without foundations’ (1967), but with no interplay between them. The remaining seven papers apparently tackle unrelated themes. Some of this disjointedness would (...) doubtless have been addressed, if Putnam had been able to compose his replies to these papers; sadly, he died before this was possible. In this review, I do my best to tease out some connections between the paper; and there are some really interesting connections to be made. (shrink)

Synchronic norms of theory choice, a traditional concern in scientific methodology, restrict the theories one can choose in light of given information. Diachronic norms of theory change, as studied in belief revision, restrict how one should change one’s current beliefs in light of new information. Learning norms concern how best to arrive at true beliefs. In this paper, we undertake to forge some rigorous logical relations between the three topics. Concerning, we explicate inductive truth conduciveness in terms of optimally direct (...) convergence to the truth, where optimal directness is explicated in terms of reversals and cycles of opinion prior to convergence. Concerning, we explicate Ockham’s razor and related principles of choice in terms of the information topology of the empirical problem context and show that the principles are necessary for reversal or cycle optimal convergence to the truth. Concerning, we weaken the standard principles of agm belief revision theory in intuitive ways that are also necessary for reversal or cycle optimal convergence. Then we show that some of our weakened principles of change entail corresponding principles of choice, completing the triangle of relations between,, and. (shrink)

Occam’s razor directs us to adopt the simplest hypothesis consistent with the evidence. Learning theory provides a precise definition of the inductive simplicity of a hypothesis for a given learning problem. This definition specifies a learning method that implements an inductive version of Occam’s razor. As a case study, we apply Occam’s inductive razor to causal learning. We consider two causal learning problems: learning a causal graph structure that presents global causal connections among a set of domain variables, and learning (...) context-sensitive causal relationships that hold not globally, but only relative to a context. For causal graph learning, Occam’s inductive razor directs us to adopt the model that explains the observed correlations with a minimum number of direct causal connections. For expanding a causal graph structure to include context-sensitive relationships, Occam’s inductive razor directs us to adopt the expansion that explains the observed correlations with a minimum number of free parameters. This is equivalent to explaining the correlations with a minimum number of probabilistic logical rules. The paper provides a gentle introduction to the learning-theoretic definition of inductive simplicity and the application of Occam’s razor for causal learning. (shrink)

Synchronic norms of theory choice, a traditional concern in scientific methodology, restrict the theories one can choose in light of given information. Diachronic norms of theory change, as studied in belief revision, restrict how one should change one’s current beliefs in light of new information. Learning norms concern how best to arrive at true beliefs. In this paper, we undertake to forge some rigorous logical relations between the three topics. Concerning, we explicate inductive truth conduciveness in terms of optimally direct (...) convergence to the truth, where optimal directness is explicated in terms of reversals and cycles of opinion prior to convergence. Concerning, we explicate Ockham’s razor and related principles of choice in terms of the information topology of the empirical problem context and show that the principles are necessary for reversal or cycle optimal convergence to the truth. Concerning, we weaken the standard principles of agm belief revision theory in intuitive ways that are also necessary for reversal or cycle optimal convergence. Then we show that some of our weakened principles of change entail corresponding principles of choice, completing the triangle of relations between,, and. (shrink)

A critical survey of some attempts to define ‘computer’, beginning with some informal ones, then critically evaluating those of three philosophers, and concluding with an examination of whether the brain and the universe are computers.

Ebbhinghaus, H., J. Flum, and W. Thomas. 1984. Mathematical Logic. New York, NY: Springer-Verlag. Forster, T. Typescript. The significance of Yablo’s paradox without self-reference. Available from http://www.dpmms.cam.ac.uk. Gold, M. 1965. Limiting recursion. Journal of Symbolic Logic 30: 28–47. Karp, C. 1964. Languages with Expressions of Infinite Length. Amsterdam.

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)

Let d be a Turing degree containing differences of recursively enumerable sets (d.r.e.sets) and R[d] be the class of less than d r.e. degrees in whichd is relatively enumerable (r.e.). A.H.Lachlan proved that for any non-recursive d.r.e. d R[d] is not empty. We show that the r.e. degree defined by Lachlan for a d.r.e.set $D\in$ d is just the minimum degree in which D is r.e. Then we study for a given d.r.e. degree d class R[d] and show that there (...) exists a d.r.e.d such that R d] has a minimum element $>$ 0. The most striking result of the paper is the existence of d.r.e. degrees for which R[d] consists of one element. Finally we prove that for some d.r.e. d R[d] can be the interval [a,b] for some r.e. degrees a,b, a $<$ b $<$ d. (shrink)

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more (...) mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)

Przedmowa Problematyka związana z zależnościami przyczynowymi, ich modelowaniem i odkrywa¬niem, po długiej nieobecności w filozofii i metodologii nauk, budzi współcześnie duże zainteresowanie. Wiąże się to przede wszystkim z dynamicznym rozwojem, zwłaszcza od lat 1990., technik obli¬czeniowych. Wypracowane w tym czasie sieci bayesowskie uznaje się za matematyczny język przyczynowości. Pozwalają one na daleko idącą auto¬matyzację wnioskowań, co jest także zachętą do podjęcia prób algorytmiza¬cji odkrywania przyczyn. Na potrzeby badań naukowych, które pozwalają na przeprowadzenie eksperymentu z randomizacją, standardowe metody ustalania zależności przyczynowych (...) opracowano na początku XX wieku. Zupełnie inaczej sprawa przedstawia się w przypadku badań nieeksperymentalnych, gdzie podobne rozwiązania pozostają kwestią przyszłości. Zadaniem tej książki jest podanie warunków, które powinny być spełnione przez te rozwiązania, oraz sformułowanie proceduralnego kryterium zależności przy¬czynowych jako szczegółowej realizacji tych warunków. Pociąga ono waż¬kie konsekwencje dla filozofii i metodologii nauk, które ujawnia – podany w Części II – zarys me-todolo¬gii proceduralnej. W literaturze przedmiotu brakuje w miarę wszechstronnego i systema¬tycznego omówie¬nia najnowszych filozoficznych i metodologicznych dys¬kusji na temat przy¬czynowości, co niech będzie wytłumaczeniem, dlaczego w niektórych punktach obecnej książki szczegółowo referuję trudno dos¬tępne teksty źró¬dłowe. Przymiotnik „proceduralny” używam tu w znaczeniu węższym niż Huw Price (w którego pracach właściwszy byłby termin „kryterialny”) dla podkre¬ślenia – zgodnie z łacińskim źródłosłowem procedo – że dla ustalenia przy¬czyny niezbędne jest podjęcie przez uczonych określonych interakcji z ba¬daną rzeczywistością. Zalążki zamysłu prezentowanego w tej książce przedstawiłem podczas warsztatów filozoficznych „Philosophy and Probability” w roku 2002, zor¬ganizowanych przez Instytut Filozofii Uniwersytetu w Konstancji. Wdzięczny jestem uczestnikom tych warsztatów za uwagi, a przede wszyst¬kim następującym osobom: Luc Bovens, Brandon Fitelson, Alan Hájek, Stephan Hartmann oraz Jon Williamson. Podczas międzynarodowej konferencji „Analytical Pragmatism”, zorgani¬zowanej w Lublinie w roku 2003 przez Wydział Filo¬zofii Katolickiego Uniwersytetu Lubelskiego, odniosłem swoją koncepcję do prac Nancy Cartwright. Szczególnie inspirujący okazał się komentarz Huw Price’a do mojego referatu i przeprowadzona z nim dysku¬sja. Ujęcie koncepcji metodologii proceduralnej na szerszym tle współ-czes¬nego nurtu empirystycznego w filozofii nauki przedstawiłem w roku 2004 podczas konferencji „5th Quadrennial Fellows Conference”, zorgani¬zowanej przez Instytut Filozofii Uniwersytetu Jagiellońskiego oraz Centrum Filozofii Nauki w Pittsburghu. Szczególnie pomocne w dalszych moich pra¬cach były uwagi Jamesa Bogena, Janet Kourany, Jamesa Lennoxa, Johna Nortona, Thomasa Bonka, Jana Woleńskiego i Johna Worralla, za które wyra¬żam swoją wdzięczność. Korpus książki powstał podczas mojego stażu w Centrum Filozofii Nauki w Pittsburghu, który odbyłem jako stypendysta Fundacji na Rzecz Nauki Polskiej w roku akademickim 2004-2005. Uczestniczyłem w tym czasie w życiu naukowym Centrum i w pracach badawczych zespołu z Instytutu Filozofii Uniwersytetu Carnegie-Mellon w Pittsburghu kierowanego przez Clarka Glymoura. Na jego ręce składam podziękowanie za wiele po¬mocnych uwag do moich wy¬stąpień oraz tekstów i za dyskusje przede wszystkim z nim samym i z jego najbliższymi współpracownikami: Peterem Spirtesem oraz Richardem Scheinesem, a także pozostałymi członkami tego zes¬połu, doktorantami i uczestnikami seminarium badawczego „Causality in the Social Sciences”. Za wieloletnie wsparcie, wielopłaszczyznowe inspiracje towarzyszące pi¬saniu tej książki, a także liczne pomocne uwagi do jej wcześniejszych wersji dziękuję przede wszystkim Księdzu Profesorowi Andrzejowi Bronkowi oraz Księdzu Profesorowi Józefowi Herbutowi, współprowadzącemu seminarium doktorskie w Katedrze Metodologii Nauk Katolickiego Uniwersytetu Lubel¬skiego im. Jana Pawła II, jak również pozostałym uczestnikom tego semina¬rium. Dziękuję mojej Żonie, dr Annie Kawalec za wiele wysiłku włożonego w ulepszenie redakcji – językowej i merytorycznej – obecnej książki. Książkę tę można czytać na kilka sposobów. Czytelnikom zainteresowa¬nym przede wszystkim prowadzeniem badań empirycznych polecałbym rozpoczęcie od Rozdziału 2. i kontynuację pozostałych rozdziałów Części I, a następnie Dodatków. Czytelnikom zainteresowanym problemami filozo¬fii i metodologii nauk polecałbym rozpoczęcie lektury książki od Części II i uzupełniającą lekturę Rozdziału 2., a następnie Wprowadzenia i Zakończenia. Czytelnikom mniej zainteresowanym zagadnieniami teoretycznymi pole¬całbym zapoznanie się z fascynującymi dziejami odkrycia przyczyn cholery przez Johna Snowa, które rekonstruuję w Rozdziale 1. W dalszej części nato¬miast polecałbym przejście do Wprowadzenia i Zakończenia, które w mniej specjalistyczny sposób przybliżają proponowane tu rozstrzygnięcia. Tekst książki nie był dotąd publikowany. Wyjątkiem są pewne fragmenty Rozdziału 8. oraz 9., które w zmienionej postaci ukazały się w Rocznikach Filozoficznych (Kawalec 2004). -/- Lublin, luty 2006 r. (shrink)

Ockham’s razor is the principle that, all other things being equal, scientists ought to prefer simpler theories. In recent years, philosophers have argued that simpler theories make better predictions, possess theoretical virtues like explanatory power, and have other pragmatic virtues like computational tractability. However, such arguments fail to explain how and why a preference for simplicity can help one find true theories in scientific inquiry, unless one already assumes that the truth is simple. One new solution to that problem is (...) the Ockham efficiency theorem, which states that scientists who heed Ockham’s razor retract their opinions less often and sooner than do their non-Ockham competitors. The theorem neglects, however, to consider competitors following random strategies and in many applications random strategies are known to achieve better worst-case loss than deterministic strategies. In this paper, we describe two ways to extend the result to a very general class of random, empirical strategies. The first extension concerns expected retractions, retraction times, and errors and the second extension concerns retractions in chance, times of retractions in chance, and chances of errors. (shrink)

Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...) Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

Showcasing original arguments for well-defined positions, as well as clear and concise statements of sophisticated philosophical views, this volume is an ...

Some think that issues to do with scientific method are last century's stale debate; Popper was an advocate of methodology, but Kuhn, Feyerabend, and others are alleged to have brought the debate about its status to an end. The papers in this volume show that issues in methodology are still very much alive. Some of the papers reinvestigate issues in the debate over methodology, while others set out new ways in which the debate has developed in the last decade. The (...) book will be of interest to philosophers and scientists alike in the reassessment it provides of earlier debates about method and current directions of research. (shrink)

We analyse the extent of possible computations following Hogarth ([2004]) conducted in Malament–Hogarth (MH) spacetimes, and Etesi and Németi ([2002]) in the special subclass containing rotating Kerr black holes. Hogarth ([1994]) had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi ([2002]) had shown that some relations on natural numbers that are neither universal nor co-universal, can be decided in Kerr spacetimes, and had asked specifically as to the extent of computational limits there. (...) The purpose of this note is to address this question, and further show that MH spacetimes can compute far beyond the arithmetic: effectively Borel statements (so hyperarithmetic in second-order number theory, or the structure of analysis) can likewise be resolved: Theorem A. If H is any hyperarithmetic predicate on integers, then there is an MH spacetime in which any query ? n H ? can be computed. In one sense this is best possible, as there is an upper bound to computational ability in any spacetime, which is thus a universal constant of that spacetime. Theorem C. Assuming the (modest and standard) requirement that spacetime manifolds be paracompact and Hausdorff, for any spacetime there will be a countable ordinal upper bound, , on the complexity of questions in the Borel hierarchy computable in it. Introduction 1.1 History and preliminaries Hyperarithmetic Computations in MH Spacetimes 2.1 Generalising SADn regions 2.2 The complexity of questions decidable in Kerr spacetimes An Upper Bound on Computational Complexity for Each Spacetime CiteULike Connotea Del.icio.us What's this? (shrink)

1. Characterizing randomness. Consider a physical process that, if suitably idealized, generates an indefinite sequence of independent random bits. One such process might be radioactive decay of a lump of uranium whose mass is kept at just the level needed to ensure that the probability is one-half that no alpha particle is emitted in the nth microsecond of the experiment. Let us think of the bits as drawn from {0, 1} and denote the resulting sequence by x with coordinates x0, (...) x1, . . .. Now wouldn’t it be odd if there were a computer program P with the following property? (shrink)

This paper describes the corner-stones of a means-ends approach to the philosophy of inductive inference. I begin with a fallibilist ideal of convergence to the truth in the long run, or in the 'limit of inquiry'. I determine which methods are optimal for attaining additional epistemic aims (notably fast and steady convergence to the truth). Means-ends vindications of (a version of) Occam's Razor and the natural generalizations in a Goodmanian Riddle of Induction illustrate the power of this approach. The paper (...) establishes a hierarchy of means-ends notions of empirical success, and discusses a number of issues, results and applications of means-ends epistemology. (shrink)

This paper pursues a thorough-going instrumentalist, or means-ends, approach to the theory of inductive inference. I consider three epistemic aims: convergence to a correct theory, fast convergence to a correct theory and steady convergence to a correct theory (avoiding retractions). For each of these, two questions arise: (1) What is the structure of inductive problems in which these aims are feasible? (2) When feasible, what are the inference methods that attain them? Formal learning theory provides the tools for a complete (...) set of answers to these questions. As an illustration of the results, I apply means-ends analysis to various versions of Goodman's Riddle of Induction. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

We investigate the degree spectra of computable relations on canonically ordered natural numbers $$(\omega,<)$$ ( ω, < ) and integers $$(\zeta,<)$$ ( ζ, < ). As for $$(\omega,<)$$ ( ω, < ), we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all $$\Delta _2$$ Δ 2 degrees; this includes the complete characterization of the degree spectra of so-called computable block functions that have only finitely many types of blocks. Compared to Bazhenov (...) et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022), we obtain a more general solution to the problem regarding possible degree spectra on $$(\omega,<)$$ ( ω, < ), answering the question whether there are infinitely many such spectra. As for $$(\zeta,<)$$ ( ζ, < ), we prove the following dichotomy result: given an arbitrary computable relation R on $$(\zeta,<)$$ ( ζ, < ), its degree spectrum is either trivial or it contains all c.e. degrees. This result, and the proof techniques required to solve it, extend the analogous theorem for $$(\omega,<)$$ ( ω, < ) obtained by Wright (Computability 7:349–365, 2018), and provide initial insight to Wright’s question whether such a dichotomy holds on computable ill-founded linear orders. This article is an extended version of Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022). (shrink)

The background of this paper (section 1) consists in a new account to foundation‐theoretic epistemology characterized by two features: (i) All beliefs are to be justified by deductive, inductive or abductive inferences from a minimalistic class of unproblematic (introspective or analytic) basic beliefs. (ii) Higher‐order justifications for these inferences are given by means of the novel method of optimality justifications. Optimality justifications are a new tool for epistemology (section 2). An optimality justification does not attempt todemonstratethat a cognitive method is (...) reliable (which is impossible), but pursues the more modest goal of demonstrating that the method isoptimalamong all accessible alternative methods for the given epistemic goal. The reasoning from the established optimality of a method to the acceptability of a particular belief generated by the method is accomplished by so‐called optimality principles. In sections 3–5, the method of optimality justifications is carried out in detail for three fundamental problems: justifying induction, logic, and theory‐generating abduction. (shrink)

In the framework of Stewart Shapiro, computations are performed directly on strings of symbols (numerals) whose abstract numerical interpretation is determined by a notation. Shapiro showed that a total unary function (unary relation) on natural numbers is computable in every injective notation if and only if it is almost constant or almost identity function (finite or co-finite set). We obtain a syntactic generalization of this theorem, in terms of quantifier-free definability, for functions and relations relatively intrinsically computable on certain types (...) of equivalence structures. We also characterize the class of relations and partial functions of arbitrary finite arities which are computable in every notation (be it injective or not). We consider the same question for notations in which certain equivalence relations are assumed to be computable. Finally, we discuss connections with a theorem by Ash, Knight, Manasse and Slaman which allow us to deduce some (but not all) of our results, based on quantifier elimination. (shrink)

Both early analytic philosophy and the branch of mathematics now known as topology were gestated and born in the early part of the 20th century. It is not well recognized that there was early interaction between the communities practicing and developing these fields. We trace the history of how topological ideas entered into analytic philosophy through two migrations, an earlier one conceiving of topology geometrically and a later one conceiving of topology algebraically. This allows us to reassess the influence and (...) significance of topological methods for philosophy, including the possible fruitfulness of a third conception of topology as a structure determining similarity. (shrink)

– We offer a new motivation for imprecise probabilities. We argue that there are propositions to which precise probability cannot be assigned, but to which imprecise probability can be assigned. In such cases the alternative to imprecise probability is not precise probability, but no probability at all. And an imprecise probability is substantially better than no probability at all. Our argument is based on the mathematical phenomenon of non-measurable sets. Non-measurable propositions cannot receive precise probabilities, but there is a natural (...) way for them to receive imprecise probabilities. The mathematics of non-measurable sets is arcane, but its epistemological import is far-reaching; even apparently mundane propositions are liable to be affected by non-measurability. The phenomenon of non-measurability dramatically reshapes the dialectic between critics and proponents of imprecise credence. Non-measurability offers natural rejoinders to prominent critics of imprecise credence. Non-measurability even reverses some of the critics’ arguments—by the very lights that have been used to argue against imprecise credences, imprecise credences are better than precise credences. (shrink)

O presente volume se trata de uma coletânea de artigos que reúne alguns dos trabalhos propostos para o evento “III International Colloquium of Analytic Epistemology and VII Conference of Social Epistemology”, realizado entre os dias 27 e 30 de Novembro de 2018, na Universidade Federal de Santa Maria. O “III International Colloquium of Analytic Epistemology and VII Conference of Social Epistemology” é um dos principais eventos de Epistemologia analítica da América Latina e reúne especialistas do Brasil e do exterior para (...) promover debates de alto nível sobre temas que fazem parte da agenda contemporânea no que se refere ao debate analítico contemporâneo acerca da Epistemologia. (shrink)

The notion of an ideal reasoner has several uses in epistemology. Often, ideal reasoners are used as a parameter of (maximum) rationality for finite reasoners (e.g. humans). However, the notion of an ideal reasoner is normally construed in such a high degree of idealization (e.g. infinite/unbounded memory) that this use is unadvised. In this dissertation, I investigate the conditions under which an ideal reasoner may be used as a parameter of rationality for finite reasoners. In addition, I present and justify (...) the research program of computational epistemology, which investigates the parameter of maximum rationality for finite reasoners using computer simulations. (shrink)

When Ken Malone investigates a case of something causing mental static across the United States, he is teleported to a world that doesn't exist.

In this paper we prove that the preordering $\lesssim $ of provable implication over any recursively enumerable theory $T$ containing a modicum of arithmetic is uniformly dense. This means that we can find a recursive extensional density function $F$ for $\lesssim $. A recursive function $F$ is a density function if it computes, for $A$ and $B$ with $A\lnsim B$, an element $C$ such that $A\lnsim C\lnsim B$. The function is extensional if it preserves $T$-provable equivalence. Secondly, we prove a (...) general result that implies that, for extensions of elementary arithmetic, the ordering $\lesssim $ restricted to $\Sigma_{n}$-sentences is uniformly dense. In the last section we provide historical notes and background material. (shrink)

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...) the MathML sourceΔ20-piecewise computability, and learnability is equivalent to countable View the MathML sourceΠ10-piecewise computability . Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/ Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games. (shrink)

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals on (...) Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14. (shrink)

We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].

Various proposals have suggested that an adequate explanatory theory should reduce the number or the cardinality of the set of logically independent claims that need be accepted in order to entail a body of data. A (and perhaps the only) well-formed proposal of this kind is William Kneale’s: an explanatory theory should be finitely axiomatizable but it’s set of logical consequences in the data language should not be finitely axiomatizable. Craig and Vaught showed that Kneale theories (almost) always exist for (...) any recursively enumerable but not finitely axiomatizable set of data sentences in a first order language with identity. Kneale’s criterion underdetermines explanation even given all possible data in the data language; gratuitous axioms may be “tacked on.” Define a Kneale theory, T, to be logically minimal if it is deducible from every Kneale theory (in the vocabulary of T) that entails the same statements in the data language as does T. If they exist, minimal Kneale theories are candidates for best explanations: they are “bold” in a sense close to Popper’s; some minimal Kneale theory is true if any Kneale theory is true; the minimal Kneale theory that is data equivalent to any given Kneale theory is unique; and no Kneale theory is more probable than some minimal Kneale theory. I show that under the Craig-Vaught conditions, no minimal Kneale theories exist. (shrink)

Formal learning theory is the mathematical embodiment of a normative epistemology. It deals with the question of how an agent should use observations about her environment to arrive at correct and informative conclusions. Philosophers such as Putnam, Glymour and Kelly have developed learning theory as a normative framework for scientific reasoning and inductive inference.

Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.

A natural problem from elementary arithmetic which is so strongly undecidable that it is not even Trial and Error decidable (in other words, not decidable in the limit) is presented. As a corollary, a natural, elementary arithmetical property which makes a difference between intuitionistic and classical theories is isolated.

Diagonalization is a proof technique that formal learning theorists use to show that inductive problems are unsolvable. The technique intuitively requires the construction of the mathematical equivalent of a "Cartesian demon" that fools the scientist no matter how he proceeds. A natural question that arises is whether diagonalization is complete. That is, given an arbitrary unsolvable inductive problem, does an invincible demon exist? The answer to that question turns out to depend upon what axioms of set theory we adopt. The (...) two main results of the paper show that if we assume ZermeloFraenkel set theory plus AC and CH, there exist undetermined inductive games. The existence of such games entails that diagonalization is incomplete. On the other hand, if we assume the Axiom of Determinacy, or even a weaker axiom known as Wadge Determinacy, then diagonalization is complete. In order to prove the results, inductive inquiry is viewed as an infinitary game played between the scientist and nature. Such games have been studied extensively by descriptive set theorists. Analogues to the results above are mentioned, in which both the scientist and the demon are restricted to computable strategies. The results exhibit a surprising connection between inductive methodology and the foundations of set theory. (shrink)