Catálogo de publicaciones - libros

The index set of computable structures with decidable theory for some fixed infinite language is –complete .

This paper presents some new results about majority games. Isbell (1959) was the first to find a majority game without a minimum normalized integer representation; he needed 12 voters to construct such a game. Since then, it has been an open problem to find the minimum number of voters of a majority game without a minimum normalized integer representation. Our main new results are:

1. All majority games with less than 9 voters have a minimum integer representation.

2. For 9 voters, there are 14 majority games without a minimum integer representation, but all these games admit a minimum normalized integer representation.

3. For 10 voters, there exist majority games with neither a minimum integer representation nor a minimum normalized integer representation.

We attempt to understand a cohomological approach to lower bounds in Boolean circuits (of [Fri05]) by studying a very restricted case; in this case Boolean complexity is described via the kernel (or nullspace) of a fairly simple linear transformation and its transpose. We look at this linear transformation approach for Boolean functions where we only allow AND gates, which is essentially the SET COVER problem. These linear transformations can recover the linear programming bound. More importantly, we learn that the optimal linear transformation to use can depend on the Boolean function whose complexity we wish to bound; we also learn that infinite complexity (that can occur in AND complexity over arbitrary sets and “bases”) appears as a limits of the linear transformation bounds.

In the paper the exact pair theorem for the -enumeration degrees is proved. As a corollary an exact pair theorem involving the jump operation for the enumeration degrees is obtained.

03D30.

This paper investigates operational semantics for various positive relevant logics without distribution after the work of Kit Fine in . To invalidate the law of distribution of conjunction over disjunction, we use different types of states to model conjunction and disjunction, respectively. The implication → is interpreted by three operations ⊕ , ⊗ , ⊝, instead of one operation ‘·’ as in Fine’s work.

Effective domain theory is applied to fuzzy logic to give suitable notions of semi-decidable and decidable -subset. The connection with the notions of fuzzy Turing machines and fuzzy grammar given in literature is also investigated. This shows the inadequateness of these definitions and the difficulties in formulating an analogue of Church Thesis for fuzzy logic.

We extend the notion of (TTE-)computability to nonstandard universes by the traditional method of enlarging universes through ultrafilters. In this way a nonstandard notion of effectivity is obtained.

We study Post’s Problem for the ordinal register machines defined in [6], showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors the results in [3] for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.

We introduce, and show the equivalences among, relativized versions of Brouwer’s fan theorem for detachable bars (FAN), weak König lemma with a uniqueness hypothesis (WKL!), and the longest path lemma with a uniqueness hypothesis (LPL!) in the spirit of constructive reverse mathematics. We prove that a computable version of minimum principle: if is a real valued computable uniformly continuous function with at most one minimum on {0,1}, then there exists a computable in {0,1} such that , is equivalent to some computably relativized version of FAN, WKL! and LPL!.

In the standard literature on inductive inference, a learner sees as input the course of values of the function to be learned. In the present work, it is investigated how reasonable this choice is and how sensitive the model is with respect to variations like the overgraph or undergraph of the function. Several implications and separations are shown and for the basic notions, a complete picture is obtained. Furthermore, relations to oracles, additional information and teams are explored.