The Hilbert–Bernays Theorem establishes that for any satisfiable first-order quantificational schema S, one can write out linguistic expressions that are guaranteed to yield a true sentence of elementary arithmetic when they are substituted for the predicate letters in S. The theorem implies that if L is a consistent, fully interpreted language rich enough to express elementary arithmetic, then a schema S is valid if and only if every sentence of L that can be obtained by substituting predicates of L for (...) predicate letters in S is true. The theorem therefore licenses us to define validity substitutionally in languages rich enough to express arithmetic. The heart of the theorem is an arithmetization of Gödel's completeness proof for first-order predicate logic. Hilbert and Bernays were the first to prove that there is such an arithmetization. Kleene established a strengthened version of it, and Kreisel, Mostowski, and Putnam refined Kleene's result. Despite the later refinements, Kleene's presentation of th.. (shrink)

We provide three new results about interpolating 2-r.e. or 2-REA degrees between given r.e. degrees: Proposition 1.13. If c h are r.e. , c is low and h is high, then there is an a h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h g there is a properly d-r.e. degree a such that h a g and a is r.e. in h . Theorem 3.1. There is an incomplete nonrecursive r.e. A (...) such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob . The second combines highness with a modified version of the proof strategy of Cooper et al. . The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction. (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)

The aim of this paper is to address the question: Can an artificial neural network (ANN) model be used as a possible characterization of the power of the human mind? We will discuss what might be the relationship between such a model and its natural counterpart. A possible characterization of the different power capabilities of the mind is suggested in terms of the information contained (in its computational complexity) or achievable by it. Such characterization takes advantage of recent results based (...) on natural neural networks (NNN) and the computational power of arbitrary artificial neural networks (ANN). The possible acceptance of neural networks as the model of the human mind's operation makes the aforementioned quite relevant. (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)

This paper develops a means–end analysis of an inductive problem that arises in particle physics: how to infer from observed reactions conservation principles that govern all reactions among elementary particles. I show that there is a reliable inference procedure that is guaranteed to arrive at an empirically adequate set of conservation principles as more and more evidence is obtained. An interesting feature of reliable procedures for finding conservation principles is that in certain precisely defined circumstances they must introduce hidden particles. (...) Among the reliable inductive methods there is a unique procedure that minimizes convergence time as well as the number of times that the method revises its conservation principles. Thus the aims of reliable, fast and steady convergence to an empirically adequate theory single out a unique optimal inference for a given set of observed reactions—including prescriptions for when exactly to introduce hidden particles. (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)

In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite computable (...) ordinal α. It is known that jump traceability and superlowness coincide on the c.e. sets and we show that for every infinite computable ordinal α, jump traceability with ‐ or ‐bound of a c.e. set A is equivalent to the fact that. Finally, we consider the generalized truth‐table reducibilities and prove that for every (not necessarily the Turing jump of a c.e. set) set A and every limit computable ordinal α, iff. (shrink)

We argue that thinking of the man-machine comparison in terms of a contest involves, in a reasonable scenario, a criterion of success that is neutral. This is because we want to avoid a petitio principii. We submit, however, that, by looking at things this way, one makes the most essential human things invisible. Thus, in a sense, the contest approach is self-defeating.

Theoria, Volume 87, Issue 4, Page 986-1000, August 2021.

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)

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)

A finite data set is consistent with infinitely many alternative theories. Scientific realists recommend that we prefer the simplest one. Anti-realists ask how a fixed simplicity bias could track the truth when the truth might be complex. It is no solution to impose a prior probability distribution biased toward simplicity, for such a distribution merely embodies the bias at issue without explaining its efficacy. In this note, I argue, on the basis of computational learning theory, that a fixed simplicity bias (...) is necessary if inquiry is to converge to the right answer efficiently, whatever the right answer might be. Efficiency is understood in the sense of minimizing the least fixed bound on retractions or errors prior to convergence. (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.

In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive (...) ordinal α. (shrink)

In this paper, the contributions to the account of meta-induction (Schurz 2019) collected in this volume are critically discussed and thereby, new insights are developed. How broad and expandable the program of meta-induction is can be learned from Ortner’s contribution. New insights about the transition from the a priori justification of meta-induction to the a posteriori justification of object-induction emerge from the reflection of Shogenji’s paper. How meta-induction may be applied also to religious prophecies and that their meta-inductive justification does (...) not fail for a priori reasons but because of missing evidence for predictive success is learned from the discussion of Pitts’ contribution. That meta-induction does not rely on a particular prior distribution, while the no free lunch theorem depends implicitly on a uniform prior, is the major conclusion drawn from the discussion of Wolpert’s article. How the problem of induction is treated in different versions of the Bayesian account is learned from the discussion of Willliamson’s paper. That meta-induction can also be employed for abduction, and that abductive theory-revision can offer meta-inductive aggregation methods is a new insight emerging from the reflection of Aliseda’s contribution. (shrink)

LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.

Trail-And-Error machines have been proposed by Hintikka and Mutanen as an alternative formulation of the notion of computation. These machines extend the capabilities of the Turing machine and widen the theory of computation.

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.

White (2015) proposes an a priori justification of the reliability of inductive prediction methods based on his thesis of induction-friendliness. It asserts that there are by far more induction-friendly event sequences than induction-unfriendly event sequences. In this paper I contrast White's thesis with the famous no free lunch (NFL) theorem. I explain two versions of this theorem, the strong NFL theorem applying to binary and the weak NFL theorem applying to real-valued predictions. I show that both versions refute the thesis (...) of induction-friendliness. In the conclusion I argue that an a priori justification of the reliability of induction based on a uniform probability distribution over possible event sequences is impossible. In the outlook I consider two alternative approaches: (i) justification externalism and (ii) optimality justifications. (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)

Criteria of approximate scientific success are defined within a formal paradigm of empirical inquiry. One consequence of aiming for less than perfect truth is examined.

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set ℐ of the sentences that get limit probability 1 is a Π3—theory, in fact ℐ can be a Π3—complete set. We prove incompleteness results for this setting, by showing for instance that for every k > 0 there are true Π3—sentences that get limit probability less than 1/2k. No set (...) ℐ as above can contain the set of all true Π3—sentences, although we exhibit some ℐ containing all the true Σ2—sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. (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)

I propose that empirical procedures, like computational procedures, are justified in terms of truth-finding efficiency. I contrast the idea with more standard philosophies of science and illustrate it by deriving Ockham's razor from the aim of minimizing dramatic changes of opinion en route to the truth.

In a paper published in 1975, Robert Jeroslow introduced the concept of an experimental logic as a generalization of ordinary formal systems such that theoremhood is a (or in practice ) rather than . These systems can be viewed as (rather crude) representations of axiomatic theories evolving stepwise over time. Similar ideas can be found in papers by Putnam (1965) and McCarthy and Shapiro (1987). The topic of the present article is a discussion of a suggestion by Allen Hazen, that (...) these experimental logics might provide an illuminating way of representing “the human mathematical mind”. This is done in the context of the well-known Lucas-Penrose thesis. Though we agree that Jeroslow's model has some merit in this context, and that the Lucas-Penrose arguments certainly are less than persuasive, some semi-technical doubts are raised concerning the alleged impact of experimental logics on the question of knowable self-consistency. (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)

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)

We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and (...) can be -complete. These classifications are exact. For first order theories even finite sets of premises can generate such consequence sets in either calculus. (shrink)

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)

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)

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)