By theword problemfor some class of algebraic structures we mean the problem of determining, given a finite setEof equations between words and an additional equationx=y, whetherx=ymust hold in all structures satisfying each member ofE. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable forcancellation semigroups,i.e. semigroups satisfying thecancellation propertyNovikov [N] eventually showed the word problem for groups to be undecidable.In 1966 (...) Gurevich [G] showed the word problem to be undecidable forfinitesemigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero satisfying an approximation to the cancellation property. (shrink)

This book taps the best American thinkers to answer the essential American question: How do we sustain our experiment in government of, by, and for the people? Authored by an extraordinary and politically diverse roster of public officials, scholars, and educators, these chapters describe our nation's civic education problem, assess its causes, offer an agenda for reform, and explain the high stakes at risk if we fail.

The first collection of Leibniz's key writings on the binary system, newly translated, with many previously unpublished in any language. -/- The polymath Gottfried Wilhelm Leibniz (1646–1716) is known for his independent invention of the calculus in 1675. Another major—although less studied—mathematical contribution by Leibniz is his invention of binary arithmetic, the representational basis for today's digital computing. This book offers the first collection of Leibniz's most important writings on the binary system, all newly translated by the authors with many (...) previously unpublished in any language. Taken together, these thirty-two texts tell the story of binary as Leibniz conceived it, from his first youthful writings on the subject to the mature development and publication of the binary system. -/- As befits a scholarly edition, Strickland and Lewis have not only returned to Leibniz's original manuscripts in preparing their translations, but also provided full critical apparatus. In addition to extensive annotations, each text is accompanied by a detailed introductory “headnote” that explains the context and content. Additional mathematical commentaries offer readers deep dives into Leibniz's mathematical thinking. The texts are prefaced by a lengthy and detailed introductory essay, in which Strickland and Lewis trace Leibniz's development of binary, place it in its historical context, and chart its posthumous influence, most notably on shaping our own computer age. (shrink)

The problem of consciousness arises when we accept that humans are subject to conscious experiences, and that these experiences resist explanations of a kind that other puzzling phenomena permit. I first consider the case that such experiences exist and then the reasons for taking a pessimistic view of our chances of explaining them. I argue that the fact that conscious experience is ineffable makes the problem even harder than Chalmers allows, as it undermines a presentation of the problem of reductive (...) explanation in this case. The fact that conscious phenomena require a first-person perspective provides a further reason for taking a pessimistic view of the chances for the kind of theory that Chalmers seeks. In a final section I consider what form solutions to the problem, as revised, might take. (shrink)

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite (...) models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types. (shrink)

It is common in the history of science to try to extend an idea first demonstrated in one domain into others. Sometimes the extension is literal, and sometimes it is frankly metaphorical. Sometimes, however, when an extension is claimed to be literal, it is far from easy to see that it is. If an extension does not make use of entities and mechanisms involved in the original domain, and introduces novel entities and mechanisms, then it is not unreasonable to doubt (...) the claim of its authors that it is a literal extension of a well-established theory. IT is, therefore, not surprising that many who accept that the cultural transmission of information is unique to out species nevertheless balk at Dawkins's and Dennett's contention that there are units of cultural evolution, called 'memes', which can be used to explain the development and diversity of human culture, and whose survival is explicable in terms of Darwin's theory of evolution by natural selection. Our aim in this paper is to argue that scepticism about Dawkins's and Dennett's proposal is indeed justified; though it of course does not follow that there is not another way of explaining human culture in evolutionary terms. (shrink)

It has been proposed by Dawkins, Dennett and others that memes are the units of cultural evolution. We here concentrate on Dennett's account because of the role it plays in his explanation of human consciousness - which is our principal target. Memes are claimed to be replicators that work on Darwinian principles. But in what sense are they replicators, and in what way are they responsible for their own propagation? We argue that their ability to replicate themselves is severely limited, (...) particularly in the case of language-borne memes. We contend, too, that the theory has unacceptable consequences for the role of design in accounting for cultural change, unless we seriously want to entertain the thought that design has as little relevance to cultural evolution as it does to the evolution of species. Finally, we argue that the account fails to do justice to the complexities of social practices. (shrink)