LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a (...) function with oracleK. (shrink)

The relativized propositional calculus is a system of Boolean formulas with query symbols. A formula in this system is called a one-query formula if the number of occurrences of query symbols is just one. If a one-query formula is a tautology with respect to a given oracle A then it is called a one-query tautology with respect to A. By extending works of Ambos-Spies (1986) and us (2002), we investigate the measure of the class of all oracles A such that (...) the set of all one-query tautologies with respect to A does not p-btt-reduce to A, where p-btt denotes polynomial-time bounded-truth-table. We show that certain Dowd-type generic oracles all belong to the class, and hence measure of the class is one. (shrink)

Call a set A n-correctable if every set Turing reducible to A via a Turing machine that on any input makes at most n queries is Turing reducible to A via a Turing machine that on any input makes at most n-queries and on any input halts no matter what answers are given to its queries. We show that if a c.e. set A is n-correctable for some n ≥ 2, then it is n-correctable for all n. (...) We show that this is the optimal such result by constructing a c.e. set that is 1-correctable but not 2-correctable. The former result is obtained by examining the logical closure properties of c.e. sets that are 2-correctable. (shrink)

We investigate the connection between interference and computational power within the operationally defined framework of generalised probabilistic theories. To compare the computational abilities of different theories within this framework we show that any theory satisfying four natural physical principles possess a well-defined oracle model. Indeed, we prove a subroutine theorem for oracles in such theories which is a necessary condition for the oracle model to be well-defined. The four principles are: causality, purification, strong symmetry, and informationally consistent composition. Sorkin has (...) defined a hierarchy of conceivable interference behaviours, where the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. Given our oracle model, we show that if a classical computer requires at least n queries to solve a learning problem, because fewer queries provide no information about the solution, then the corresponding “no-information” lower bound in theories lying at the kth level of Sorkin’s hierarchy is \. This lower bound leaves open the possibility that quantum oracles are less powerful than general probabilistic oracles, although it is not known whether the lower bound is achievable in general. Hence searches for higher-order interference are not only foundationally motivated, but constitute a search for a computational resource that might have power beyond that offered by quantum computation. (shrink)

We develop a bounded version of the finite injury priority method in recursion theory. We use this to study the learnability of unions of rectangles over the domain {0, …, n − 1}d with only equivalence queries. Applying this method, we show three main results:1. The class of unions of rectangles is polynomial time learnable for constant dimension d.2. The class of unions of rectangles whose projections at some unknown dimension are pairwise-disjoint is polynomial time learnable.3. The class (...) of unions of two disjoint rectangles is polynomial time learnable with unions of two rectangles as hypotheses. (shrink)

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, . The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, . Additionally, we resolve an open (...) question in [7] about passive versus active learning. (shrink)

The object of this paper is to explain a certain type of construction which occurs in priority proofs and illustrate it with two examples due to Lachlan and Harrington. The proofs in the examples are essentially the original proofs; our main contribution is to isolate the common part of these proofs. The key ideas in this common part are due to Lachlan; we include several improvements due to Harrington, Soare, Slaman, and the author.Our notation is fairly standard. If X is (...) an r.e. set, Xs is the finite set of elements enumerated in X before step s. if Ф is a recursive functional, Фs is the approximation to Ф at step s; it only queries the oracle about numbers xi and iless-than-or-equals, slantx; and right-pointing angle bracketx0,...,xk−1right-pointing angle bracket is an increasing function of each of its arguments. Sets are sometimes identified with their characteristic functions. Wj isthe jth r.e. set. Xc is the complement of X. (shrink)

This work deals with the expressive power of logics on finite graphs with access to an additional "arbitrary" linear order. The queries that can be expressed this way are the order-invariant queries for the logic. For the standard logics used in computer science, such as first-order logic, it is known that access to an arbitrary linear order increases the expressiveness of the logic. However, when we look at the separating examples, we find that they have satisfying models whose (...) Gaifman Graph is complex -unbounded in valence and in treewidth. We thus explore the expressiveness of order-invariant queries over well-behaved graphs. We prove that first-order order-invariant queries over strings and trees have no additional expressiveness over first-order logic in the original signature. We also prove new upper bounds on order-invariant queries over bounded treewidth and bounded valence graphs. Our results make use of a new technique of independent interest: the application of algebraic characterizations of definability to show collapse results. (shrink)

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant (...) version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective. (shrink)

In Opticks, Newton notes that by following the method of analysis and synthesis, ’the bounds of moral philosophy will also be enlarged’. Hume’s Treatise fulfills this vision, albeit with significant caveats. The chapter argues: 1) Hume’s affinity with Newton is primarily methodological, and Hume’s project is closer to the Queries of Opticks than to the Principia. 2) For Hume, moral philosophy is an experimental study of moral beings qua moral beings which results in ‘an anatomy of the mind’ embodying (...) an epistemic ideal closer to Scottish philosophical chemistry than to any kind of mechanical philosophy. 3) Hume primarily inquires into qualitatively different active principles of human nature that explain why humans function as they do. 4) The knowledge that Hume’s project offers can be used normatively. 5) Thus, in Hume’s hands the boundaries of moral philosophy are enlarged. Yet, being entirely secular, it was not what Newton had envisioned. (shrink)

This paper is concerned with techniques for identifying simple and quantified lattice points in 2SAT polytopes. 2SAT polytopes generalize the polyhedra corresponding to Boolean 2SAT formulas, Vertex-Packing and Network flow problems; they find wide application in the domains of Program verification and State-Space search . Our techniques are based on the symbolic elimination strategy called the Fourier-Motzkin elimination procedure and thus have the advantages of being extremely simple and incremental. We also provide a characterization of a 2SAT polytope in terms (...) of its extreme points and derive some interesting hardness results for associated optimization problems. Finally, we provide a brief discussion on the maximum size of a subdeterminant of the linear system representing a 2SAT polytope; this parameter plays a vital role in deriving analytical bounds on the size of the search space for checking whether the polyhedron includes a lattice point. (shrink)

In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to (...) the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65–76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes. (shrink)

Abstract The increasing prevalence of armed drones in the conduct of military operations has generated robust debate. Among legal scholars, the crux of the dispute generally pits those who herald the new technology's unparalleled precision against those who view such newfound capabilities as an inducement to employ excessive force. Largely overlooked in the discussion over how drone strikes can be accomplished lawfully is a more fundamental question: Can a model of warfare that eschews any risk of harm to one party (...) be squared with the ethical framework that informs the law of war? This matter has less to do with the technology per se than with a policy orientation that utilizes such technology as a strategy in itself, as opposed to one military tool in a larger arsenal. A corollary to the incongruity of riskless warfare is to query whether the ensuing breakdown of ethical and legal norms unwittingly encourages the very instability that the law of war attempts to control, thereby endangering the civilian populations of all parties to the conflict. While other authors have previously addressed the challenges posed by asymmetry to the law of armed conflict in different formats, this article explores these issues through a hypothetical scenario and seeks to elucidate some of the potential ramifications of the pursuit of physical impunity in war. (shrink)

Let equation image. We show that for many reducibilities, the requirement that a relation be intrinsically reducible to the α-th jump of a countable mode A has a syntactic equivalent. Furthermore, we show that many reducibilities coincide in such a situation.

We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system [Formula: see text], we prove that the following statements are equivalent, (1) Provable learning. [Formula: see text] proves efficiently that p-size circuits are learnable by subexponential-size circuits over the uniform distribution with membership queries. (2) Provable automatability. [Formula: see text] proves efficiently that [Formula: see text] is automatable by non-uniform circuits on propositional formulas expressing p-size circuit lower bounds. (...) Here, [Formula: see text] is sufficiently strong and well-behaved if I.–III. hold: I. [Formula: see text] p-simulates Jeřábek’s system [Formula: see text] (which strengthens the Extended Frege system [Formula: see text] by a surjective weak pigeonhole principle); II. [Formula: see text] satisfies some basic properties of standard proof systems which p-simulate [Formula: see text]; III. [Formula: see text] proves efficiently for some Boolean function [Formula: see text] that [Formula: see text] is hard on average for circuits of subexponential size. For example, if III. holds for [Formula: see text], then Items 1 and 2 are equivalent for [Formula: see text]. We use the following modified notion of automatability in Item 2, the automating circuits output a [Formula: see text]-proof of a given formula (expressing a p-size circuit lower bound for a function [Formula: see text]) in non-uniform p-time in the length of a shortest [Formula: see text]-proof of a closely related but different formula (expressing an average-case subexponential-size circuit lower bound for the same function [Formula: see text]). If there is a function [Formula: see text] which is hard on average for circuits of size [Formula: see text], for each sufficiently big [Formula: see text], then there is an explicit propositional proof system [Formula: see text] satisfying properties I.-III., i.e. the equivalence of Items 1 and 2 holds for [Formula: see text]. (shrink)

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always (...) true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

Journal of Mathematical Logic, Ahead of Print. We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system [math], we prove that the following statements are equivalent, (1) Provable learning. [math] proves efficiently that p-size circuits are learnable by subexponential-size circuits over the uniform distribution with membership queries. (2) Provable automatability. [math] proves efficiently that [math] is automatable by non-uniform circuits on propositional formulas expressing p-size circuit lower bounds. Here, (...) [math] is sufficiently strong and well-behaved if I.–III. hold: I. [math] p-simulates Jeřábek’s system [math] (which strengthens the Extended Frege system [math] by a surjective weak pigeonhole principle); II. [math] satisfies some basic properties of standard proof systems which p-simulate [math]; III. [math] proves efficiently for some Boolean function [math] that [math] is hard on average for circuits of subexponential size. For example, if III. holds for [math], then Items 1 and 2 are equivalent for [math]. We use the following modified notion of automatability in Item 2, the automating circuits output a [math]-proof of a given formula (expressing a p-size circuit lower bound for a function [math]) in non-uniform p-time in the length of a shortest [math]-proof of a closely related but different formula (expressing an average-case subexponential-size circuit lower bound for the same function [math]). If there is a function [math] which is hard on average for circuits of size [math], for each sufficiently big [math], then there is an explicit propositional proof system [math] satisfying properties I.-III., i.e. the equivalence of Items 1 and 2 holds for [math]. (shrink)

When analyzing database query languages a roperty, of theories, the pseudo-finite homogeneity property, has been introduced and applied (cf. [3]). We show that a stable theory has the pseudo-finite homogeneity property just in case its expressive power for finite states is bounded. Moreover, we introduce the corresponding pseudo-finite saturation property and show that a theory fails to have the finite cover property if and only if it has the pseudo-finite saturation property.

We introduce multifunction algebras B i τ where τ is a set of 0 or 1-ary terms used to bound recursion lengths. We show that if for all ℓ ∈ τ we have ℓ ∈ O then B i τ = FP Σ i−1 p , those multifunctions computable in polynomial time with at most O )) queries to a Σ i−1 p witness oracle for ℓ ∈ τ and p a polynomial. We use our algebras to obtain independence (...) results in bounded arithmetic. In particular, we show if S 2 i proves Σ j b = PH for some j⩾i then S 2 i ≼ B S 2 . This implies if P NP ≠ P NP then S 2 1 does not prove the polynomial hierarchy collapses. We then consider a subtheory, Z , of the well-studied bounded arithmetic theory S 2 = ∪ i S 2 i . Using our algebras we establish the following properties of this theory: Z cannot prove the polynomial hierarchy collapses. In fact, even Z+ Π ̂ 0 b -consequences of S 2 cannot prove the hierarchy collapses. If Z ⊆ S 2 i for any i then the polynomial hierarchy collapses. If Z proves the polynomial hierarchy is infinite then for all i , S 2 i ⊢ Σ i p ≠ Π i p. (shrink)

VI. International Leibniz-Congress to be held at the University of Hannover, 18-23 July, 1994: This is organized by the Gottfried-Wilhelm-Leibniz-Gesellschaft, the Leibniz Society of North America, the Sociedad Española Leibniz, and the Niedersächsische Landesbibliothek Hannover. The opening lecture will be given by Professor N. Rescher. The organizers invite all interested researchers, experts in the field, and friends to participate. Sectional contributions should be submitted by 15 December 1993. The texts of accepted contributions, bound and photocopied, will be available at the (...) opening of the Congress. The manuscripts to be reproduced must be submitted no later than 1 March 1994. Precise directions for the presentation of manuscripts will be sent to contributors following registration. The registration fee is 80.— DM. Copies of the sectional contributions will be included in the conference material. Queries should be directed to the Gottfried-Wilhelm-Leibniz-Gesellschaft, Niedersächsische Landes-bibliothek, Waterloostr. 8, D-30169 Hannover. (shrink)

In many areas of scientific inquiry, the phenomena under investigation are viewed as functions on the real numbers. Since observational precision is limited, it makes sense to view these phenomena as bounded functions on the rationals. One may translate the basic notions of recursion theory into this framework by first interpreting a partial recursive function as a function on Q. The standard notions of inductive inference carry over as well, with no change in the theory. When considering the class (...) of computable functions on Q, there are a number of natural ways in which to define the distance between two functions. We utilize standard metrics to explore notions of approximate inference — our inference machines will attempt to guess values which converge to the correct answer in these metrics. We show that the new inference notions, NV∞, EX∞, and BC∞, infer more classes of functions than their standard counterparts, NV, EX, and BC. Furthermore, we give precise inclusions between the new inference notions and those in the standard inference hierarchy. We also explore weaker notions of approximate inference, leading to inference hierarchies analogous to the EXn and BCn hierarchies. Oracle inductive inference is also considered, and we give sufficient conditions under which approximate inference from a generic oracle G is equivalent to approximate inference with only finitely many queries to G. (shrink)

We analyse the extent of possible computations following Hogarth ([2004]) conducted in Malament–Hogarth (MH) spacetimes, and Etesi and Németi ([2002]) in the special subclass containing rotating Kerr black holes. Hogarth ([1994]) had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi ([2002]) had shown that some relations on natural numbers that are neither universal nor co-universal, can be decided in Kerr spacetimes, and had asked specifically as to the extent of computational limits there. (...) The purpose of this note is to address this question, and further show that MH spacetimes can compute far beyond the arithmetic: effectively Borel statements (so hyperarithmetic in second-order number theory, or the structure of analysis) can likewise be resolved: Theorem A. If H is any hyperarithmetic predicate on integers, then there is an MH spacetime in which any query ? n H ? can be computed. In one sense this is best possible, as there is an upper bound to computational ability in any spacetime, which is thus a universal constant of that spacetime. Theorem C. Assuming the (modest and standard) requirement that spacetime manifolds be paracompact and Hausdorff, for any spacetime there will be a countable ordinal upper bound, , on the complexity of questions in the Borel hierarchy computable in it. Introduction 1.1 History and preliminaries Hyperarithmetic Computations in MH Spacetimes 2.1 Generalising SADn regions 2.2 The complexity of questions decidable in Kerr spacetimes An Upper Bound on Computational Complexity for Each Spacetime CiteULike Connotea Del.icio.us What's this? (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are algorithmically solvable (...) for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

Indirect negative evidence is clearly an important way for learners to constrain overgeneralisation, and yet a good learning theoretic analysis has yet to be provided for this, whether in a PAC or a probabilistic identification in the limit framework. In this paper we suggest a theoretical analysis of indirect negative evidence that allows the presence of ungrammatical strings in the input and also accounts for the relationship between grammaticality/acceptability and probability. Given independently justified assumptions about lower bounds on the probabilities (...) of grammatical strings, we establish that a limited number of membership queries of some strings can be probabilistically simulated. (shrink)

A hypertext learner navigates with a instinctive feeling for a knowledge. The learner does not know her queries, although she has a feeling for them. A learner’s navigation appears as complete upon the emergence of an aesthetic pleasure, called rasa. The order of arrival or the associational logic and even the temporal order are not relevant to this emergence. The completeness of aesthetics is important. The learner does not look for the intention of the writer, neither does she look (...) for significance. Lexia has a suggestive power and she is suggested in the arrival of aesthetics. Hypertext learning does not depend on communication. The learner in her pleasure transgresses the bounds of space-time to be in communion with several writers/learners. Hypertext learning does not appear to be fundamentally different from the analog learning; however, in performance, as in navigation, the learner assumes a mental state that helps her in her emergence into aesthetic bliss, of an arrival to the completed lexial navigation. This completeness is owing to aesthetics and is not owing to either the semantics or the query-fulfilling qualities. (shrink)

A set Asubset of or equal toω is called computably enumerable , if there is an algorithm to enumerate the elements of it. For sets A,Bsubset of or equal toω, we say that A is bounded Turing reducible to reducible to) B if there is a Turing functional, Φ say, with a computable bound of oracle query bits such that A is computed by Φ equipped with an oracle B, written image. Let image be the structure of the c.e. (...) bT-degrees, the c.e. degrees under the bounded Turing reductions. In this paper we study the continuity properties in image. We show that for any c.e. bT-degree image, there is a c.e. bT-degree image such that for any c.e. bT-degree image, image if and only if image. We prove that the analog of the Seetapun local noncappability theorem from the c.e. Turing degrees also holds in image. This theorem demonstrates that every image is noncappable with any nontrivial degree below some image. (shrink)

For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{(x_1, \dots ,x_n): {\tt\#}^A_n(x_1, \dots, x_n) \text{is odd}\}$ and, for m ≥ 2, $\text{MOD}m^A_n = \{(x_1, \dots ,x_n):{\tt\#}^A_n(x_1, \dots ,x_n) \not\equiv 0 (\text{mod} m)\},$ where ${\tt\#}^A_n(x_1, \dots ,x_n) = A(x_1)+\cdots+A(x_n)$ . (We identify A(x) with χ A (x), where χ A (...) is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODD A n and $\text{MOD}m^A_n: \bullet\text{ODD}^A_n$ can be decided with n parallel queries to A, but not with n - 1. $\bullet \text{ODD}^A_n$ can be decided with $\lceil log(n + 1)\rceil$ sequential queries to A but not with $\lceil log(n + 1)\rceil - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil n/m\rceil + \lfloor n/m\rfloor$ parallel queries to A but not with $\lceil n/m\rceil + \lfloor n/m\rfloor - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil log(\lceil n/m\rceil + \lfloor n/m\rfloor + 1)\rceil$ sequential queries to A but not with $\lceil log(\lceil n/m\rceil + \lfloor n/m\rfloor + 1)\rceil - 1$ . The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODD A n cannot be decided with n - 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODD B n can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, $Q(n,A) = \{S: S \text{can be decided with n sequential queries to} A\},\\Q_\parallel(n, A) = \{S: S \text{can be decided with n parallel queries to} A\}.$ We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: $\bullet Q(0,A) \subset Q(1,A) \subset Q(2,A) \subset\cdots\\ \bullet Q_\parallel(0, A) \subset Q_\parallel(1, A) \subset Q_\parallel(2,A) \subset\cdots$ The same is true if A is a jump. (shrink)

In lieu of an abstract, here is a brief excerpt of the content: Choice and Virtue in the Nicomachean Ethics ALFRED R. MELE COM~rNTATORS ON THr Nicomachean Ethics (NE) have long been laboring under the influence of a serious misunderstanding of one of the key terms in Aristotle's moral philosophy and theory of action. This term is prohairesis (choice), the importance of which is indicated by Aristotle's assertions that choice is the proximate efficient cause of action (NE 6. 1139a31--32) and (...) that in which "the essential elements of virtue and character" lie (NE 8. x163a2'~-23). The accepted view is that Aristotle employs two importantly different notions of choice in the NE, one on which the term refers exclusively to means or things which are pros (toward, related to)' ends and another on which it does not have this reference? This "two notion" interpretation is motivated by the following three considerations: i. Aristotle's good or virtuous agent is said (NE 2. 11o5a28-33, cf. NE 6. 1144ax8-2o ) to choose actions for their own sakes; but, according to the This paper is derived in part from a chapter of my doctoral dissertation, which was submitted to the University of Michigan in January of 1979. 1 would like to express my gratitttde to the chairman of my dissertation committee, Nicholas P. White, for his comments and criticisms on the relevant sections during the preparation of my dissertation and to theJHP's anonymous reviewers for their helpful criticisms and queries. ' It has often been pointed out that things which are pros an end are not necessarily "means," in the ordinary sense of the word. E.g., constituents of an end are pros the end, but they are not means to it. See, e.g., Nicomachean Ethics, Book 6, trans. Leonard H. G. Greenwood (Cambridge: Cambridge University Press, 19o9), pp. 46-47, 53ff.: and John M. Cooper, Reason and Human Good in Aristotle (Cambridge: Harvard University Press, 1975), pp. 1o-22. ' Among the many proponents of this "two notion" interpretation are William D. Ross and Donald J. Allan. See Ross, Aristotle, 5th ed. (London: Methuen, t953), p. 2oo. See Allan, The Philosophy of Aristotle, 2nd ed. (London: Oxford University Press, 197o), p. 132; idem, "Aristotle 's Account of the Origin of Moral Principles," Xlth International Congress of Philosophy 12 (1953):124; idem, "The Practical Syllogism," in Autour d'Aristote, Studies for A. Mansion (Louvain : Publications Universitaires, 1955). Richard Sorabji, in "Aristotle on the Role of Intellect in Virtue" (Proceedings of the Aristotelian Society 74 l t973-74]:t t6), says that he has noticed sixteen commentators who take this view. [4o5] 406 HISTORY OF PHILOSOPHY so-called formal account of prohairesis (NE 3. 2-3, 6. 2), the object of choice is what has been decided upon by deliberation (bouleuais), and what is decided upon by deliberation is a "means" to an end. 2. Aristotle says that choice is "closely bound up with virtue" and "discriminates characters better than actions do" (1 1t lb5; cf. t i lob3t, 1117a 5, 1163a22, 1t64bi); but commentators argue that these claims about choice are false unless choice is "of ends." 3. Though Aristotle holds that the impetuous akrat~s (incontinent agent) does not deliberate (e.g., t 152a 18-19), he says that the akrat~s' choice is good (1152ax5--17; cf. l l51a5-- 7, 29--32); and this appears to contradict his position in Book 3 that the object of choice is what is decided upon by deliberation, s In this paper I shall show that only one (philosophically significant) notion ofprohairesis is employed in the NE, namely, the notion developed in the "formal account" of deliberation and choice (3- 2-3, 6. 2), according to which choice is specifically of things which are pros ends. This point has several interesting applications. For example, it makes it easier to find in Aristotle (as I shall briefly explain) a comprehensive theory of practical reasoning or inference rather than several unconnected accounts of what practical inference is like in different types of cases; and it is helpful in clarifying what is involved in the evaluation of character on Aristotle's view (see Sec. ~). However, though I do think that the main point to be made... (shrink)

Law clings to rules to stabilize a preferred normative reality. But rules never suffice. Character is the dark matter of law. Ethos anthropos daimon. “Character is fate.” This paradoxically reversible saying by the ancient Greek philosopher Heraclitus asserts that we are defined by the daimon – the god or messenger angel – with which we identify most. As Plato queried in the Phaedrus: which god do you follow, whose love claims you? In contemporary terms we might say, what character type, (...) what emotional ideal, what deep story do you hold most sacred? Out of the maelstrom that is the state of exception, choices must be made. What emotional field shall we occupy when we do politics and law? Bound by what sovereign values or ideals, embodied within what sort of character, emplotted in what sort of political or legal narrative? In synergy with culture, character plays out the emotional conflicts and aspirations of the time. Whether we witness this in the mostly silent resistance of unassimilable characters like Barnardine in Shakespeare’s Measure for Measure or in the silent prayer of nineteen-year-old Emma Gonzalez, in public protest against uncontrolled gun violence in American schools, we are all called upon, as citizens in public life, to occupy an emotional space that attains centrality within deep narratives that vie for political dominance. Reverse engineering liberal society, we might ask: what emotional and character ideals are optimal in order for a particular kind of political society to arise and be sustained? There is a reciprocal relationship between the sovereign authority of law and the character ideals that express a capacity and willingness to accept that authority. What will the configuration be? Addressing this question constitutes the ethical, esthetic, and epistemological calling of our time. (shrink)

The Copernican revolution with which Kant transformed the question of whether knowledge is possible into the query as to how knowledge is possible, constitutes one stage in the development of epistemology from a speculative to an observational science — i.e., one that proceeds from the investigation of concrete, existent objects rather than from a small number of presupposed concepts. This path, leading from speculation to examination of the concrete objects of research — for epistemology, to the investigation of the various (...) individual sciences — is long and arduous, and even now it has been traversed only a small part of the way. Although epistemological research has for a long time had some relation to mathematics and physics, and a more concrete exploration of biology and the humanities has recently been launched as well, we undoubtedly still stand at the very beginning of this enterprise. One major task for the epistemological inquiry into a specific discipline is bound up with tracing the course of development of that science — in particular, the radical shifts and readjustments in a science that promise to furnish the epistemologist with valuable information. Seen from this angle, psychology also currently deserves the special attention of epistemology. (shrink)

Reviewed Works:Andrea Sorbi, Complexity, Logic, and Recursion Theory.Klaus Ambos-Spies, Elvira Mayordomo, Resource-Bounded Measure and Randomness.Marat Arslanov, Degree Structures in Local Degree Theory.Jose L. Balcazar, Ricard Gavalda, Montserrat Hermo, Compressibility of Infinite Binary Sequences.S. Barry Cooper, Beyond Godel's Theorem: The Failure to Capture Information Content.Robert A. Di Paola, Franco Montagna, Progressions of Theories of Bounded Arithmetic.Rodney G. Downey, On Presentations of Algebraic Structures.Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet, Witness-Isomorphic Reductions and Local Search.William Gasarch, Carl H. Smith, A Survey of (...) Inductive Inference with an Emphasis on Queries.Andre Nies, A Uniformity of Degree Structures.Piergiorgio Odifreddi, Short Course on Logic, Algebra, and Topology.Andrea Sorbi, The Enumeration Degrees of the $\sigma^0_2$ Sets.Peter van Emde Boas, The Convenience of Tilings. (shrink)

This volume presents the proceedings of the workshop CSL '91 (Computer Science Logic) held at the University of Berne, Switzerland, October 7-11, 1991. This was the fifth in a series of annual workshops on computer sciencelogic (the first four are recorded in LNCS volumes 329, 385, 440, and 533). The volume contains 33 invited and selected papers on a variety of logical topics in computer science, including abstract datatypes, bounded theories, complexity results, cut elimination, denotational semantics, infinitary queries, (...) Kleene algebra with recursion, minimal proofs, normal forms in infinite-valued logic, ordinal processes, persistent Petri nets, plausibility logic, program synthesis systems, quantifier hierarchies, semantics of modularization, stable logic, term rewriting systems, termination of logic programs, transitive closure logic, variants of resolution, and many others. (shrink)

In a multiagent and multi-cultural world, the fine-grained analysis of agents’ dynamic behaviour, i.e. of their activities, is essential. Dynamic activities are actions that are characterized by an agent who executes the action and by other participants of the action. Wh-questions on the participants of the actions pose a difficult particular challenge because the variability of the types of possible answers to such questions is huge. To deal with the problem, we propose the analysis and classification of Wh-questions apt for (...) agents’ communication in a multiagent system (MAS). Our proposal of such a system consists of agents who communicate with their fellow agents by messaging so that each autonomous agent, though resource-bounded, can make less or more rational decisions to meet its own and collective goals. In addition, by communicating with other fellow agents and their environment, agents can learn new concepts and enrich their ontology so that their behaviour is dynamic. We aim to make a general proposal of the system so that the ‘envelope’ of agents’ messages can be formalized in any MAS standard, be it The Foundation for Intelligent Physical Agents - Agent Communication Language (FIPA-ACL) or Knowledge Query and Manipulation Language (KQML). Yet, the content of messages is encoded in a formalized natural language. To this end, we apply Transparent Intensional Logic (TIL) with its procedural semantics which is particularly apt for a fine-grained analysis in which all the semantically salient features of natural language can be plausibly formalized. In this paper, we concentrate on analysing the content of query messages, particularly the content of those that encode Wh-questions and the answers to them. We also summarize TIL deduction system that makes it possible to answer such questions in an intelligent way. Linguists distinguish several subtypes of Wh-questions. Though the linguistic classification is helpful, it is not always suitable for agents’ communication and reasoning. We need the classification based on a logical analysis of Wh-questions so that the agents can infer possible answers to such questions rather than only looking for them by keywords. This paper aims to apply an appropriate classification of the logical types of Wh-questions and the analysis of such questions; we concentrate in particular on questions concerning the participants of activities. The application of these results to the analysis of processes and events based on verb valency frames is another novelty of the paper. (shrink)

Two-player, zero-sum, non-cooperative, blindfold games in extensive form with incomplete information are considered in this paper. Any information about past moves which players played is stored in a database, and each player can access the database. A polynomial game is a game in which, at each step, all players withdraw at most a polynomial amount of previous information from the database. We show resource-bounded determinacy of some kinds of finite, zero-sum, polynomial games whose pay-off sets are computable by non-deterministic (...) polynomial-time function-oracle Turing machines. We call a pay-off set -determined if, for any polynomial game G associated with the given pay-off set, either player has a winning strategy which is in for any subgames of G. We show that there exists an FP-strongly-determined pay-off set which is computed by an exponential-time oracle Turing machine, where FP is the set of polynomial-time computable functions. We also discuss several relationships between the determinacy of polynomial games and recursion-theoretic properties for the classes co-NP and co-NEXP. We show that the polynomial version of the axiom of choice holds under some assumption of polynomial determinacy for a pay-off set which is polynomial-time computable with parallel queries. This principle of choice implies that co-NP has the separation property. (shrink)

We consider Choiceless Polynomial Time , a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting from image. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank (...) of sets used, even in image, an extension of image with counting. (shrink)

We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results.• Although (...) Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time.• Although for every universal machine U, there are very complex sets that are -reducible to , it is nonetheless true that . • Any decidable set that is polynomial-time monotone-truth-table reducible to is in .• Any decidable set that is polynomial-time truth-table reducible to via a reduction that asks at most f queries on inputs of size n lies in. (shrink)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...) assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

This article examines whether the gender balance on the High Court of Australia has disrupted the gender regime. In so doing it considers the first lead judgments of the three women judges who sat concurrently on the High Court of Australia between 2009 and early 2015. The High Court has adopted an interesting informal practice of welcoming new judges whereby the newest member authors the lead judgment and their judicial colleagues offer a one-line concurrence. The way in which judicial authority (...) is conferred in these judgments is reminiscent of the space in political spheres where an incumbent has their first opportunity to set out their identity and agenda in a speech free of the noise of dissent or debate; the ‘maiden’ speech. In that space the price an incumbent pays for comity is conformity. This article contends that the first judgment is a useful way of situating a discussion about women judges’ contributions vis-à-vis difference by querying the extent to which the woman judge can ever shake-off her status as the maiden bound to conform for the sake of comity. (shrink)

Abstract Galileo Then and Now (Draft of paper to be discussed at the Conference, HPD1, to be held at the Center for Philosophy of Science, University of Pittsburgh, 11-14 October 2007) William R. Shea, University of Padua The aim of this paper is to stimulate discussion on how shifts in philosophical fashion and societal moods tell us not only what to read but how to go about it, and how history and philosophy of science can jointly deepen our grasp of (...) the issues at stake. The first part highlights some of the things that have occurred in the field of Galileo studies between the monumental edition of Galileo Opere in twenty volumes, edited by Antonio Favaro between 1890 and 1909, and the new enlarged edition that will be published from 2009 onwards by a team of scholars working under Paolo Galluzzi. Part One. From Favaro to Galluzzi "Publish or perish" is an injunction that resonated as clearly in the ears of assistant professors at the end of the 19th century as it does in the first decade of the 21st. But publishing can also mean perishing when what is being edited is the work of an eminent scientist of the past. It simply does not do to offer material that is not what readers expect even if it was written by someone as famous as Galileo, and well authenticated sources were sometimes disregarded when they appeared to be of no interest. It is largely for this reason that a new national edition of Galileo's works is required. Of course, over the last hundred years, a number of letters from and to Galileo as well as a few laudatory or damning comments about his personality or his work have been uncovered, but this would not have been enough to drum up financial and scholarly support for a major editorial project. But the interesting material is Favaro had left out. Before mentioning what this material is, allow me a disclaimer. I'm not focusing on Favaro because he is a singularity, but because he illustrates how a conscientious historian can ride slipshod over evidence because of a philosophical commitment that he is only vaguely aware of, in this case naïve positivism. So what did Favaro to leave out? The answer is large chunks of three collections of manuscript notes that are bound in some of the 347 volumes of the Galilean material in the National Library in Florence. The first of these collections deals with logical treatises and related essays on Aristotelian philosophy, the second with Galileo's laboratory notes on the experiments that he carried out on the pendulum and inclined planes; and the third with astrological computations. Favaro rejected the first collection because they were "pre-Galilean" and hence could only have been trite scholastic exercises that "poor" young Galileo had to undergo in high school. He neglected the second because he had trouble making sense of them The third, astrological collection, he set aside with more trepidation since Galileo cast horoscopes for himself (at least twice), his children and his friends. But the fact that they were also, epistemologically speaking, "pre-Galilean", was enough to cast them into the outer darkness (in this case a dimly lit corridor of the National Library in Florence). The Aristotelian notes that Favaro had neglected were made available by William Wallace, who showed that Galileo culled long passages from professors at the Roman College. Galileo attacked several of Aristotle's ideas, but he never queried Aristotle's scientific realism–namely, the view that there is a uniquely true physical theory, discovered by human powers of reason and observation, and that alternative theories are consequently falls. Wallace made this the basis of his claim that Galileo created, in the heaven above and here on earth, a new science of motion by following the Aristotelian cannons laid down in the Posterior Analytics. On this view, Galileo used Aristotle's logic to subvert Aristotelian physics. It is interesting to contrast Wallace's thesis with that of philosophers of different allegiance, who offer a reconstruction of Galileo's methodology along lines that are much more modern and in which the epistemological core is no longer Aristotelian logic, but common sense instrumentalism. This is not to deny that experiments sometimes speak with a forked tongue, but to stress that methodological rules have also been known to be no more than clashing cymbals. Recent writers have also stressed that Galileo aimed his arguments at a specific audience, and that we must take cognizance of the values and whims of the society in which he operated. The sociology of science can help us understand the background against which Galileo's arguments were assessed and the reasons why he favored some rhetorical strategies over other ones. Mario Biagoli's Galileo Courtier sheds light on the Tuscan court and the Roman famiglia (as the popes styled their entourage), where Galileo found many of his readers and most of his critics. But Galileo was much more than a courtier, and I shall argue that we should use our enhanced knowledge of Galileo's education, his language, his style, and his emoluments to understand his science, not to supplant it. History and philosophy of science can combine their insights to achieve a more critical and balanced view of what actually occurred and why. (shrink)

The evolution of philosophy and physics seem to acknowledge that "informational existentialism" will be possible. Therefore, this contribution aims to comprehend if Heidegger existentialism can enrich the bound between information theory and the intercultural dialogue as regards to information. Even so, an important query arises: why specifically Heidegger's philosophy? Because it highlights an intercultural dialogue namely with East Asian and with Arabic philosophy, which is also consistent with the debate concerning the potential value and contribution of information theory to the (...) intercultural dialogue. Therefore, this manuscript intends to understand if information is shaping worldwide cultures as a consequence of its existence. (shrink)

The problem of data privacy is to verify that confidential information stored in an information system is not provided to unauthorized users and, therefore, personal and other sensitive data remain private. One way to guarantee this is to distort a knowledge base such that it does not reveal sensitive information. In the present paper we will give a universal definition of the problem of knowledge base distortion. It is universal in the sense that is independent of any particular knowledge representation (...) formalism. We will then present a basic and general algorithm for knowledge base distortion to guarantee data privacy. This algorithm provides us with upper bounds for the complexity of the distortion problem. Moreover, we examine heuristics to improve its average performance. (shrink)

The story of the body. Fay Bound Alberti takes the human body apart in order to put it back anew, telling the cultural history of our key organs and systems from the inside out, from blood to guts, brains to sex organs.