We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.

The Hanf number for a set S of sentences in \ is the least infinite cardinal \ such that for all \, if \ has models in all infinite cardinalities less than \, then it has models of all infinite cardinalities. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is \. The same argument proves that \ is the Hanf number for Scott sentences of hyperarithmetical structures.

Let f(1)=2, f(2)=4, and let f(n+1)=f(n)! for every integer n≥2. Edmund Landau's conjecture states that the set P(n^2+1) of primes of the form n^2+1 is infinite. Landau's conjecture implies the following unproven statement Φ: card(P(n^2+1))<ω ⇒ P(n^2+1)⊆[2,f(7)]. Let B denote the system of equations: {x_j!=x_k: i,k∈{1,...,9}}∪{x_i⋅x_j=x_k: i,j,k∈{1,...,9}}. The system of equations {x_1!=x_1, x_1 \cdot x_1=x_2, x_2!=x_3, x_3!=x_4, x_4!=x_5, x_5!=x_6, x_6!=x_7, x_7!=x_8, x_8!=x_9} has exactly two solutions in positive integers x_1,...,x_9, namely (1,...,1) and (f(1),...,f(9)). No known system S⊆B with a finite (...) number of solutions in positive integers x_1,...,x_9 has a solution (x_1,...,x_9)∈(N\{0})^9 satisfying max(x_1,...,x_9)>f(9). For every known system S⊆B, if the finiteness/infiniteness of the set {(x_1,...,x_9)∈(N\{0})^9: (x_1,...,x_9) solves S} is unknown, then the statement ∃ x_1,...,x_9∈N\{0} ((x_1,...,x_9) solves S)∧(max(x_1,...,x_9)>f(9)) remains unproven. Let Λ denote the statement: if the system of equations {x_2!=x_3, x_3!=x_4, x_5!=x_6, x_8!=x_9, x_1 \cdot x_1=x_2, x_3 \cdot x_5=x_6, x_4 \cdot x_8=x_9, x_5 \cdot x_7=x_8} has at most finitely many solutions in positive integers x_1,...,x_9, then each such solution (x_1,...,x_9) satisfies x_1,...,x_9≤f(9). The statement Λ is equivalent to the statement Φ. It heuristically justifies the statement Φ . This justification does not yield the finiteness/infiniteness of P(n^2+1). We present a new heuristic argument for the infiniteness of P(n^2+1), which is not based on the statement Φ. Algorithms always terminate. We explain the distinction between existing algorithms (i.e. algorithms whose existence is provable in ZFC) and known algorithms (i.e. algorithms whose definition is constructive and currently known). Assuming that the infiniteness of a set X⊆N is false or unproven, we define which elements of X are classified as known. No known set X⊆N satisfies Conditions (1)-(4) and is widely known in number theory or naturally defined, where this term has only informal meaning. *** (1) A known algorithm with no input returns an integer n satisfying card(X)<ω ⇒ X⊆(-∞,n]. (2) A known algorithm for every k∈N decides whether or not k∈X. (3) No known algorithm with no input returns the logical value of the statement card(X)=ω. (4) There are many elements of X and it is conjectured, though so far unproven, that X is infinite. (5) X is naturally defined. The infiniteness of X is false or unproven. X has the simplest definition among known sets Y⊆N with the same set of known elements. *** Conditions (2)-(5) hold for X=P(n^2+1). The statement Φ implies Condition (1) for X=P(n^2+1). The set X={n∈N: the interval [-1,n] contains more than 29.5+\frac{11!}{3n+1}⋅sin(n) primes of the form k!+1} satisfies Conditions (1)-(5) except the requirement that X is naturally defined. 501893∈X. Condition (1) holds with n=501893. card(X∩[0,501893])=159827. X∩[501894,∞)= {n∈N: the interval [-1,n] contains at least 30 primes of the form k!+1}. We present a table that shows satisfiable conjunctions of the form #(Condition 1) ∧ (Condition 2) ∧ #(Condition 3) ∧ (Condition 4) ∧ #(Condition 5), where # denotes the negation ¬ or the absence of any symbol. No set X⊆N will satisfy Conditions (1)-(4) forever, if for every algorithm with no input, at some future day, a computer will be able to execute this algorithm in 1 second or less. The physical limits of computation disprove this assumption. (shrink)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.

The class $$\mathsf{TPA}$$ TPA of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of $$\mathsf{TPA}$$ TPA nor the first order theory of $$\mathsf{TPA}$$ TPA are decidable. Moreover, we show that the set of all equations valid in $$\mathsf{TPA}$$ TPA is exactly on the $$\Pi ^1_1$$ Π 1 1 level. We consider the class $$\mathsf{TPA}^-$$ (...) TPA - of the relation algebra reducts of $$\mathsf{TPA}$$ TPA ’s, as well. We prove that the equational theory of $$\mathsf{TPA}^-$$ TPA - is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (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)

In this paper we explain our pretense account of truth-talk and apply it in a diagnosis and treatment of the Liar Paradox. We begin by assuming that some form of deflationism is the correct approach to the topic of truth. We then briefly motivate the idea that all T-deflationists should endorse a fictionalist view of truth-talk, and, after distinguishing pretense-involving fictionalism (PIF) from error- theoretic fictionalism (ETF), explain the merits of the former over the latter. After presenting the basic framework (...) of our PIF account of truth-talk, we demonstrate a few advantages it offers over T-deflationist accounts that do not explicitly acknowledge pretense at work in the discourse. In turning to the Liar Paradox, we explain how the quasi-anaphoric functioning that our account attributes to truth-talk provides a diagnosis of the Liar Paradox (and other instances of semantic pathology) as having no content—in the sense of not specifying any of what we call M-conditions. At the same time, however, we vindicate the intuition that we can understand liar sentences, thereby avoiding one standard objection to “meaningless strategy” responses to the Liar Paradox. With this diagnosis in place, we then, by way of treatment, introduce a new predicate, ‘semantically defective’, and show how the explanation we give for its application allows for a consistent, yet revenge-immune, (dis)solution of the Liar Paradox, and semantic pathology generally. (shrink)

Turing computation over a non-linguistic domain presupposes a notation for the domain. Accordingly, computability theory studies notations for various non-linguistic domains. It illuminates how different ways of representing a domain support different finite mechanical procedures over that domain. Formal definitions and theorems yield a principled classification of notations based upon their computational properties. To understand computability theory, we must recognize that representation is a key target of mathematical inquiry. We must also recognize that computability theory is an intensional enterprise: it (...) studies entities as represented in certain ways, rather than entities detached from any means of representing them. (shrink)

An early, very preliminary edition of this book was circulated in 1962 under the title Set-theoretical Structures in Science. There are many reasons for maintaining that such structures play a role in the philosophy of science. Perhaps the best is that they provide the right setting for investigating problems of representation and invariance in any systematic part of science, past or present. Examples are easy to cite. Sophisticated analysis of the nature of representation in perception is to be found already (...) in Plato and Aristotle. One of the great intellectual triumphs of the nineteenth century was the mechanical explanation of such familiar concepts as temperature and pressure by their representation in terms of the motion of particles. A more disturbing change of viewpoint was the realization at the beginning of the twentieth century that the separate invariant properties of space and time must be replaced by the space-time invariants of Einstein's special relativity. Another example, the focus of the longest chapter in this book, is controversy extending over several centuries on the proper representation of probability. The six major positions on this question are critically examined. Topics covered in other chapters include an unusually detailed treatment of theoretical and experimental work on visual space, the two senses of invariance represented by weak and strong reversibility of causal processes, and the representation of hidden variables in quantum mechanics. The final chapter concentrates on different kinds of representations of language, concluding with some empirical results on brain-wave representations of words and sentences. (shrink)

The ‘Turing barrier’ is an evocative image for 0′, the degree of the unsolvability of the halting problem for Turing machines—equivalently, of the undecidability of Peano Arithmetic. The ‘barrier’ metaphor conveys the idea that effective computability is impaired by restrictions that could be removed by infinite methods. Assuming that the undecidability of PA is essentially depending on the finite nature of its computational means, decidability would be restored by the ω-rule. Hypercomputation, the hypothetical realization of infinitary machines through relativistic and (...) quantium models, would thus be capable of breaking the Turing barrier. The speculation is unfounded in principle, apart from issues of physical realizability: The point is that the ω-rule does not cope with all objects entailing the undecidability of PA. As long as the system is consistent, the computational boundary can be established by paradox-like constructions, such as Gödel-Rosser’s and Yablo’s, which are refractory to infinite induction, and do stand as the barrier’s buttresses. (shrink)

The appropriate methodology for psychological research depends on whether one is studying mental algorithms or their implementation. Mental algorithms are abstract specifications of the steps taken by procedures that run in the mind. Implementational issues concern the speed and reliability of these procedures. The algorithmic level can be explored only by studying across-task variation. This contrasts with psychology's dominant methodology of looking for within-task generalities, which is appropriate only for studying implementational issues.The implementation-algorithm distinction is related to a number of (...) other “levels” considered in cognitive science. Its realization in Anderson's ACT theory of cognition is discussed. Research at the algorithmic level is more promising because it is hard to make further fundamental scientific progress at the implementational level with the methodologies available. Protocol data, which are appropriate only for algorithm-level theories, provide a richer source than data at the implementational level. Research at the algorithmic level will also yield more insight into fundamental properties of human knowledge because it is the level at which significant learning transitions are defined.The best way to study the algorithmic level is to look for differential learning outcomes in pedagogical experiments that manipulate instructional experience. This provides control and prediction in realistically complex learning situations. The intelligent tutoring paradigm provides a particularly fruitful way to implement such experiments.The implications of this analysis for the issue of modularity of mind, the status of language, research on human/computer interaction, and connectionist models are also examined. (shrink)

This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of (...) those optimal, learned programs are provably unalterably information deficient—in some cases, deficient as to safe, algorithmic extractability/provability of the fact that they are even approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, computably axiomatizable extensions of Peano Arithmetic. (shrink)

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation image, where equation image (...) has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in equation image. (shrink)

We provide and interpret a new measure independent characterization of the Gödel speed-up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed-up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed-up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed-up. We (...) interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed-up phenomena. MSC: 03D15, 03F20. (shrink)

In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, 03D20, 03D25.