The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...) the method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs. (shrink)

An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...) of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language. (shrink)

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, then the group (...) is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive recursive structures, (...) exponential-time structures and structures with honest witnesses. (shrink)

In this paper, we study the lattice of r.e. subspaces of a recursively presented vector space V ∞ with regard to the various complexity-theoretic speed-up properties such as speedable, effectively speedable, levelable, and effectively levelable introduced by Blum and Marques. In particular, we study the interplay between an r.e. basis A for a subspace V of V ∞ and V with regard to these properties. We show for example that if A or V is speedable , then V is levelable (...) . We also show that if A is an r.e. subset of a recursive basis for V ∞ , then A is levelable iff V is speedable while it is not the case that A is levelable iff V is speedable. We also provide several contrasts between the lattice of r.e. subspaces and the lattice of r.e. sets with respect to these speed-up properties. For example, every maximal set is levelable but we show that there exist supermaximal spaces which are nonspeedable in all possible r.e. degrees as well as supermaximal spaces which are levelable in all r.e. degrees which contain levelable sets. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...) Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy. (shrink)

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through (...) finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem. (shrink)

This paper discusses an extension of Answer Set Programming called Hybrid Answer Set Programming which allows the user to reason about dynamical systems that exhibit both discrete and continuous aspects. The unique feature of Hybrid ASP is that it allows the use of ASP type rules as controls for when to apply algorithms to advance the system to the next position. That is, if the prerequisites of a rule are satisfied and the constraints of the rule are not violated, then (...) the algorithm associated with the rule is invoked. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an (...) effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence relation is computably isomorphic to (...) a p-time equivalence relation with standard universe. (shrink)

Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples of Σ04 complete sets.

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}$ of continuous functions on ${2^{\mathbb N}}$ . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random ${\Delta^0_2}$ continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any ${y \in 2^{\mathbb N}}$ , (...) there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. (shrink)

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)

Direct neurological and especially imaging-driven investigations into the structures essential to naturally occurring cognitive systems in their development and operation have motivated broadening interest in the potential for artificial consciousness modeled on these systems. This first paper in a series of three begins with a brief review of Boltuc’s (2009) “brain-based” thesis on the prospect of artificial consciousness, focusing on his formulation of h-consciousness. We then explore some of the implications of brain research on the structure of consciousness, finding limitations (...) in biological approaches to the study of consciousness. Looking past these limitations, we introduce research in artificial consciousness designed to test for the emergence of consciousness, a phenomenon beyond the purview of the study of existing biological systems. (shrink)

This third paper locates the synthetic neurorobotics research reviewed in the second paper in terms of themes introduced in the first paper. It begins with biological non-reductionism as understood by Searle. It emphasizes the role of synthetic neurorobotics studies in accessing the dynamic structure essential to consciousness with a focus on system criticality and self, develops a distinction between simulated and formal consciousness based on this emphasis, reviews Tani and colleagues' work in light of this distinction, and ends by forecasting (...) the increasing importance of synthetic neurorobotics studies for cognitive science and philosophy of mind going forward, finally in regards to most- and myth-consciousness. (shrink)

Discoverability: the urgent need of an ecology of human creativity from the prolific Lorenzo Magnani is worthy of direct attention. The message may be of special interest to philosophers, ethicists and organizing scientists involved in the development of AI and related technologies which are increasingly directed at reinforcing conditions against which Magnani directly warns, namely the “overcomputationalization” of life marked by the gradual encroachment of technologically “locked strategies” into everyday decision-making until “freedom, responsibility, and ownership of our destinies” are ceded (...) and we, in parallel, build a future fit for artifacts over human beings. Professional educators - teachers and administrators serious about teaching - and policy-makers including the concerned public, parents and social activists concerned about the effects of technologies on development and well-being may benefit, as well. (shrink)

The phenomenon of altruism extends from the biological realm to the human sociocultural realm. This article sketches a coherent outline of multiple types of altruism of progressively increasing scope that span these two realms and are grounded in an ever-expanding sense of “self.” Discussion of this framework notes difficulties associated with altruism at different levels. It links scientific ideas about the evolution of cooperation and about hierarchical order to perennial philosophical and religious concerns. It offers a conceptual background for inquiry (...) into societal challenges that call for altruistic behavior, especially the challenge of environmental and social sustainability. (shrink)

Our purpose in this article is to identify and suggest resolution for two core problematics of grounded theory. First, while grounded theory provides transparency to one part of the conceptualization process, where codes emerge directly from the data, it provides no such systematic or transparent way for gaining insight into the conceptual relationships between discovered codes. Producing a grounded theory depends not only on the definition of conceptual pieces, but the delineation of a relationship between at least two of those (...) pieces. Second, the conceptualization process of grounded theory is done in hierarchical fashion, where individual codes emerge from the data but then are used to generate insight into more general concepts and thematic statements. But various works on grounded theory have failed to provide any systematic way of using data specific levels of scale (the codes) to gain insight into more macro levels of scale (concepts and themes). We offer fractal concept analysis as a means of resolving both of these issues. By using a logic structure generator, fractal concept analysis delineates self-similar conceptual frameworks at various levels of abstraction, yielding a method for linking concepts together within and between levels of scale encountered in the grounded theory coding and categorization process. We conclude that this fractal analytic technique can bolster the aims of grounded theory as a formalized and systematic process for generating theory from empirical data. (shrink)

Wattles offers a comprehensive survey of the history of the golden rule, "Do unto others as you want others to do unto you". He traces the rule's history in contexts as diverse as the writings of Confucius and the Greek philosophers, the Bible, modern theology and philosophy, and the American "self-help" context. He concludes by offering his own synthesis of these varied understandings.

Some theories of goodness are descriptively rich: they have much to say about what makes things good. Neo-Aristotelian accounts, for instance, detail the various features that make a human being, a dog, a bee good relative to facts about those forms of life. Famously, such theories of relative goodness tend to be comparatively poor: they have little or nothing to say about what makes one kind of being better than another kind. Other theories of goodness—those that take there to be (...) absolute goodness—are comparatively rich: they offer grounds for judging some types of things better than others because they have more absolute goodness. Moorean accounts, for example, can tell us that humans and human experiences are superior to bees and blades of grass. But such theories tend to be descriptively poor: they struggle to tell us in virtue of what this is so. In this essay we motivate and flesh out a view that splits the difference between accounts of goodness as relative and accounts of goodness as absolute. Such a view holds promise only if the mechanics of this kind of metaphysics of goodness can be worked out. Here we present a view on which the paradigm for absolute goodness is God and the paradigm for each kind of relative goodness is a divine idea. (shrink)

This chapter presents the main formalism of the book, which is used in subsequent chapters to describe a variety of concepts in Husserlian phenomenology, and thereby unify them. A dynamical systems approach to Husserl is introduced, and several dynamical laws of Husserlian phenomenology are described. The first is an expectation rule according to which expectations are determined by what a person knows, sees, and does. The second is a learning rule according to which background knowledge is updated in a specific (...) way when experiences fulfill or frustrate prior expectations. In addition to these rules, a “supervenience function” is described, which associates how a thing is seen with a “trail set,” the set ways that thing is expected to look, relative to all possible ways of moving around it. This function further illustrates the explanatory dimension of phenomenology described in Chap. 2, whereby how we immanently experience things is determined by how we expect them to look relative to counterfactual movement patterns. (shrink)

Reliabilism—the view that a belief is justified iff it is produced by a reliable process—is often characterized as a form of consequentialism. Recently, critics of reliabilism have suggested that since it is a form of consequentialism, reliabilism condones a variety of problematic trade-offs involving cases where someone forms an epistemically deficient belief now that will lead her to more epistemic value later. In the present paper, we argue that the relevant argument against reliabilism fails because it equivocates. While there is (...) a sense in which reliabilism is a kind of consequentialism, it is not of a kind on which we should expect problematic trade-offs. (shrink)

A model of the neuropsychology of anxiety is proposed. The model is based in the first instance upon an analysis of the behavioural effects of the antianxiety drugs in animals. From such psychopharmacologi-cal experiments the concept of a “behavioural inhibition system” has been developed. This system responds to novel stimuli or to those associated with punishment or nonreward by inhibiting ongoing behaviour and increasing arousal and attention to the environment. It is activity in the BIS that constitutes anxiety and that (...) is reduced by antianxiety drugs. The effects of the antianxiety drugs in the brain also suggest hypotheses concerning the neural substrate of anxiety. Although the benzodiazepines and barbiturates facilitate the effects of γ-aminobutyrate, this is insufficient to explain their highly specific behavioural effects. Because of similarities between the behavioural effects of certain lesions and those of the antianxiety drugs, it is proposed that these drugs reduce anxiety by impairing the functioning of a widespread neural system including the septo-hippocampal system, the Papez circuit, the prefrontal cortex, and ascending monoaminergic and cholinergic pathways which innervate these forebrain structures. Analysis of the functions of this system suggests that it acts as a comparator: it compares predicted to actual sensory events and activates the outputs of the BIS when there is a mismatch or when the predicted event is aversive. Suggestions are made as to the functions of particular pathways within this overall brain system. The resulting theory is applied to the symptoms and treatment of anxiety in man, its relations to depression, and the personality of individuals who are susceptible to anxiety or depression. (shrink)

A simple tool is provided to assist researchers in assessing contributions to a scientific publication, for ease in evaluating which contributors qualify for authorship, and in what order the authors should be listed. The tool identifies four phases of activity leading to a publication—Conception and Design, Data Acquisition, Analysis and Interpretation, and Manuscript Preparation. By comparing a project participant’s contribution in a given phase to several specified thresholds, a score of up to five points can be assigned; the contributor’s scores (...) in all four phases are summed to yield a total “contribution score”, which is compared to a threshold to determine which contributors merit authorship. This tool may be useful in a variety of contexts in which a systematic approach to authorial credit is desired. (shrink)

Time underlies many interesting human behaviors. Thus, the question of how to represent time in connectionist models is very important. One approach is to represent time implicitly by its effects on processing rather than explicitly (as in a spatial representation). The current report develops a proposal along these lines first described by Jordan (1986) which involves the use of recurrent links in order to provide networks with a dynamic memory. In this approach, hidden unit patterns are fed back to themselves: (...) the internal representations which develop thus reflect task demands in the context of prior internal states. A set of simulations is reported which range from relatively simple problems (temporal version of XOR) to discovering syntactic/semantic features for words. The networks are able to learn interesting internal representations which incorporate task demands with memory demands: indeed, in this approach the notion of memory is inextricably bound up with task processing. These representations reveal a rich structure, which allows them to be highly context‐dependent, while also expressing generalizations across classes of items. These representations suggest a method for representing lexical categories and the type/token distinction. (shrink)