Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...) characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

We prove that a enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no $m$-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are (...) not necessarily direct or expected. (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 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 solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.

We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)

The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.

Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.

Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results.We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree computable from a weakly (...) 2-generic one. While there have been full approximation constructions of ${\rm{\Delta }}_3^0$ minimal degrees before, our proof is rather novel since it is a computable full approximation construction where both the generic and the minimal degrees are ${\rm{\Delta }}_3^0 - {\rm{\Delta }}_2^0$. (shrink)

In [Countable thin [Formula: see text] classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin [Formula: see text] classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin [Formula: see text] classes. We will prove in this paper that the c.e. degrees containing no members of thin [Formula: see text] classes are dense in the c.e. degrees. We (...) will also prove that the c.e. degrees containing members of thin [Formula: see text] classes are dense in the c.e. degrees, improving the result of Cenzer et al. mentioned above. Thus, we obtain a new natural subclass of c.e. degrees which are both dense and co-dense in the c.e. degrees, while the other such class is the class of branching c.e. degrees 113–130] for nonbranching degrees and [T. A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 155–179] for branching degrees). (shrink)

We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.

This work contributes to the program of studying effective versions of “almost-everywhere” theorems in analysis and ergodic theory via algorithmic randomness. Consider the setting of Cantor space {0,1}N with the uniform measure and the usual shift. We determine the level of randomness needed for a point so that multiple recurrence in the sense of Furstenberg into effectively closed sets P of positive measure holds for iterations starting at the point. This means that for each k∈N there is an n such (...) that n,2n,…,kn shifts of the point all end up in P. We consider multiple recurrence into closed sets that possess various degrees of effectiveness: clopen, Π10 with computable measure, and Π10. The notions of Kurtz, Schnorr, and Martin-Löf randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the k commuting shift operators on {0,1}Nk. (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.

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)

In this book R. G. Peffer tackles the challenges of finding in Marx's work an implicit moral theory, of answering claims that Marxism is incompatible with morality, and of developing the outlines of an adequate Marxist moral and social ...

In my 1990 work – Marxism, Morality, and Social Justice – I argued for four modifications of Rawls’s principles of social justice and rendered a modified version of his theory in four principles, the first of which is the Basic Rights Principle demanding the protection of people’s security and subsistence rights. In both his Political Liberalism and Justice as Fairness Rawls explicitly refers to my version of his theory, clearly accepting three of my four proposed modifications but rejecting the fourth (...) ‐‐ the demand for social and economic democracy – on grounds that it automatically justifies socialism as opposed to capitalism. I argue, contrary to Rawls, that it is not true that this demand automatically picks socialism as the preferablesocioeconomic/political system and that a Social and Economic Democracy Principle demanding workplace and neighborhood democracy is officially neutral between these two systems … although plausible empirical assumptions may, indeed, favor the former. I then significantly elaborate my second version of Rawls’s theory of social justice which is composed of the following principles arranged in a very strong order of priority : Basic Rights Principle, Equal Basic Liberties Principle, Fair Equality of Opportunity Principle, Modified Difference Principle, and Social and Economic DemocracyPrinciple. I argue that this elaborated version of the theory – which I call “Justice as Fair Rights” – is better than either Rawls’s original theory or my previous versions of it. (shrink)

Although I do not find any of Sterba's responses to my recent criticisms of his work How to Make People Just convincing, I shall not attempt to answer them point by point since this would be a boring, scholastic exercise at best.1 Rather, I shall expand upon what I believe continue to be the three major problems with Sterba's theory and explain why his recent responses to my criticisms along these lines are not adequate.

I take up the "What is equality?" controversy begun by Amartya Sen in 1979 by critically considering utility (J. S. Mill), primary goods (John Rawls), property rights (John Roemer) and basic capabilities in terms of what is to be distributed according to principles and theories of social justice. I then consider the four most general principles designed to answer issues raised by the Equality of Welfare principle, Equality of Opportunity for Welfare principle, Equality of Resources principle and Equality of Opportunity (...) for Resources principle. I consider each with respect to the more general normative principle that whatever theory of social or distributive justice we accept should be as ambition sensitive and endowment insensitive as feasible in real world circumstances. In this context I take up the problems of expensive tastes, expensive disabilities, lowered or manipulated preferences or ‘needs,’ and differential needs versus differential talents and abilities. I argue that the best solution is to adopt a modified version of Rawls’ theory which takes primary social goods as that which is to be distributed but which demands a Basic Rights principle that insures basic subsistent rights (as well as basic security rights) as the most fundamental principle of morality (and social justice), and then demands that Rawls’ Difference Principle be applied lexically to the ‘material’ goods of income, wealth, and leisure time, but done so that the social basis of self-respect is never undermined. (shrink)

For over half a century in more than a dozen books and 600 philosophical articles Kai Nielsen has developed and defended a radically egalitarian theory of social justice as well as a political vision demanding a democratic, humane form of socialism and, on an international level, a federative world socialist government embodying these values. In Globalization and Justice Nielsen applies his acute analytical abilities and his substantive theories and views to the present ongoing reality of corporate, capitalist globalization, arguing that (...) this sort of globalization is unjust in that it further disadvantages the developing world. He then argues for an alternative sort of globalization, a process that he believes could and should have, as its end goal, a democratic and humane socialist government and society on a world-wide scale. Along the way he compares his theory and vision to those of such other major contemporary thinkers as John Rawls, Jürgen Habermas, G.A. Cohen, and Richard Rorty representing, respectively, liberal egalitarianism, critical theory, analytical Marxism , and post-modern eclecticism. (shrink)

Given certain well-known empirical facts–including the Bush II administration’s motivations and its actions initiating the war – the U.S. invasion of Iraq in 2003 (and its continuing war of occupation) is not just (i.e., is not morally justified), on any standard interpretation of Just War Theory criteria for jus ad bellum. Since there was no imminent threat of attack by Iraq against the U.S., the U.S. invasion of Iraq was a Preventative or Merely Precautionary War (which is notrecognized by either (...) Just War Theory or international law as a legitimate basis for initiating a war) rather than a Preemptive War (which may sometimes be justified, if there is a real threat of imminent attack) or a Reactive War (responding to an unjustified attack from an aggressor, which is always justified). Moreover, the neo-conservative program for perpetual U.S. world domination by the weakening of other nations and the invasions of weaker nations for purposes of U.S. economic and geopolitical advantage (behind the facade of “spreading democracy and freedom”) is not morally justified. However, the moral status of the U.S. invasion of Afghanistan is much less clear. Many argue that is was morally justified according to both Just War Theory and international law, given certain well-established empirical facts; particularly, al-Qaeda’s involvement with the events of 9-11 and the Taliban government’s protection of al-Qaeda and its terrorist infrastructure within Afghanistan. On this analysis, the U.S. invasion of Afghanistan was justified as both a Reactive War (responding to an unjustified attack against primarily civilian targets) and a Preemptive War (to try to make sure that al-Qaeda did not have the opportunity to use its infrastructure in Afghanistan to arrange other attacks on civilian targets in the U.S. or other nations). But the cogency of this analysis depends on whether there were any realistic alternatives fordisrupting al-Qaeda and bringing its leaders to justice; and some argue that such alternatives did exist. Moreover, even if U.S. military intervention in Afghanistan was morally justified it is arguable that the amount and type of force used – e.g. intensive, wide-spread bombing campaigns that killed many civilians – were not justified. (shrink)