In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Informal construction -- Formal construction -- Limiting results.

We investigate the relationship of the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low 2.

A subspace V of an infinite dimensional fully effective vector space V ∞ is called decidable if V is r.e. and there exists an r.e. W such that $V \oplus W = V_\infty$ . These subspaces of V ∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V ∞ ) and the set of decidable subspaces forms a lower semilattice S(V ∞ ). We analyse S(V ∞ ) and its relationship with L(V (...) ∞ ). We show: Proposition. Let U, V, W ∈ L(V ∞ ) where U is infinite dimensional and $U \oplus V = W$ . Then there exists a decidable subspace D such that U |oplus D = W. Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces. These results allow us to show: Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V ∞ )), is undecidable. This contrasts sharply with the result for recursive sets. Finally we examine various generalizations of our results. In particular we analyse S * (V ∞ ), that is, S(V ∞ ) modulo finite dimensional subspaces. We show S * (V ∞ ) is not a lattice. (shrink)

We investigate operators which take a set X to a set relatively computably enumerable in and above X by studying which such sets X can be so mapped into the Turing degree of K. We introduce notions of nontriviality for such operators, and use these to study which additional properties can be required of sets which can be completed to the jump by given operators of this kind.

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.

We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in (...) terms of the DTIME ) and NP. (shrink)

We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 (...) 0 complete. We also look at computable presentability of these classes. (shrink)

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...) is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...) c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

We examine the multiplicity of complementation amongst subspaces of V ∞ . A subspace V is a complement of a subspace W if V ∩ W = {0} and (V ∪ W) * = V ∞ . A subspace is called fully co-r.e. if it is generated by a co-r.e. subset of a recursive basis of V ∞ . We observe that every r.e. subspace has a fully co-r.e. complement. Theorem. If S is any fully co-r.e. subspace then S has (...) a decidable complement. We give an analysis of other types of complements S may have. For example, if S is fully co-r.e. and nonrecursive, then S has a (nonrecursive) r.e. nowhere simple complement. We impose the condition of immunity upon our subspaces. Theorem. Suppose V is fully co-r.e. Then V is immune iff there exist M 1 , M 2 ∈ L(V ∞ ), with M 1 supermaximal and M 2 k-thin, such that $M_1 \oplus V = M_2 \oplus V = V_\infty$ . Corollary. Suppose V is any r.e. subspace with a fully co-r.e. immune complement W (e.g., V is maximal or V is h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such that $V \oplus W = M \oplus W = D \oplus W = V_\infty$ . We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspace V of V ∞ is nowhere sound if (i) for all Q ∈ L(V ∞ ) if $Q \supset V$ then Q = V ∞ , (ii) V is immune and (iii) every complement of V is immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces. (shrink)

Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.

We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.

R. G. Swinburne; XIII*—Personal Identity, Proceedings of the Aristotelian Society, Volume 74, Issue 1, 1 June 1974, Pages 231–247, https://doi.org/10.1093/arist.

The distinction between propositional and doxastic justification has been of undisputed theoretical importance in a wide range of contemporary epistemological debates. Yet there are a host of intimately related issues that have rarely been discussed in connection with this distinction. For instance, the distinction not only applies to an individual’s beliefs, but also to group beliefs and to various other attitudes that both groups and individuals can take: credence, commitment, suspension, faith, and hope. Moreover, discussions of propositional and doxastic justification (...) have rarely focused on broader meta-epistemological issues, and yet meta-epistemological positions can have important implications for first-order views about this distinction. This volume addresses these and other issues by bringing together 16 essays that advance the state-of-the-art thinking on propositional and doxastic justification and explore how such thinking shapes and is shaped by a range of issues previously neglected in contemporary epistemology. (shrink)

Um alinhamento responsável à alguma versão do naturalismo filosófico requer a articulação explicita e cuidadosa de um argumento em sua defesa. Em quatro passos, o texto que segue abaixo expande e examina a validade de um argumento que é frequentemente rascunhado em favor do naturalismo. Como veremos, contudo, a versão do naturalismo que esse argumento nos permite é um pouco diferente dos naturalismos filosóficos mais populares.

What I call the Doxastic Puzzle, is the impression that while each of these claims seems true, at least one of them must be false: (a) Claims of the form ‘S ought to have doxastic attitude D towards p at t’ are sometimes true at t, (b) If Φ-ing at t is not within S’s effective control at t, then it is false, at t, that ‘S ought to Φ at t’, (c) For all S, p, and t, having doxastic (...) attitude D towards p at t is not within S’s effective control at t. All three natural replies to the puzzle have been pursued. Some have claimed that doxastic attitudes like believing that p are, in fact, within our effective control, or sufficiently so. Others have claimed that doxastic ought-claims, strictly speaking, are always false. And some have denied that effective control is required for the adequacy of doxastic ought-claims in general. I here pursue and examine a different strategy. In the first part of this paper, I argue that these claims are not only each true but actually not in tension with each other in the first place. Instead of attempting to dispel the puzzle, this solution proposes to evade it instead: to solve it by properly understanding, and by thereby accepting without contradiction, all of its constitutive claims. In the second part of the paper, I argue that the evasive strategy forces us to re-think our understanding of the place of normative reasons in epistemology. More exactly, it seems to come at the cost of one central way of thinking about our reasons for having doxastic attitudes, one where such reasons are good-standing exemplars of normative reasons in general. The evasive strategy, that is, threatens to lead us very quickly to a deflationary picture of epistemic normativity: it rescues normative talk, but sacrifices normative substance. I conclude by explaining why I think this is more consequential than some have made it out to be, and by suggesting that these consequences are welcome nonetheless. (shrink)