We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals (...) on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14. (shrink)

We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and (...) resetting infinite-time register machines, and α-Turing machines for countable admissible ordinals α. (shrink)

We focus on how we should define the relevance of information to a context for information processing agents, such as oracles. We build our formalization of relevance upon works in pragmatics which refer to contextual information without giving any explicit representation of context. We use a formalization of context (due to us) in Situation Theory, and demonstrate its power in this task. We also discuss some computational aspects of this formalization.

Let ≤r and ≤sbe two binary relations on 2ℕ which are meant as reducibilities. Let both relations be closed under finite variation and consider the uniform distribution on 2ℕ, which is obtained by choosing elements of 2ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤r-cone of a randomly chosen set X, that is, the class of all sets A with A ≤rX, differs from the lower ≤s-cone of X. By c osure (...) under finite variation, the Kolmogorov 0-1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤r-cone of A is either 0 or 1; let Almostr be the class of sets for which the upper ≤r-cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2ℕ which can be defined by a countable set of total continuous functionals on 2ℕ in the same way as the usual resource-bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource-bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource-bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations. (shrink)

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a test of a known (...) physical theory T. Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge. The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol, this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity. (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)

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a test of a known (...) physical theory T.Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge.The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol; this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity. (shrink)

We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.

Extending techniques of Dowd and those of Poizat, we study computational complexity of in the case when is a generic oracle, where is a positive integer, and denotes the collection of all -query tautologies with respect to an oracle . We introduce the notion of ceiling-generic oracles, as a generalization of Dowd's notion of -generic oracles to arbitrary finitely testable arithmetical predicates. We study how existence of ceiling-generic oracles affects behavior of a generic oracle, by which we (...) show that is not a subset of is comeager in the Cantor space. Moreover, using ceiling-generic oracles, we present an alternative proof of the fact (Dowd) that the class of all -generic oracles has Lebesgue measure zero. (shrink)

While it is well known that a Turing machine equipped with the ability to flip a fair coin cannot compute more than a standard Turing machine, we show that this is not true for a biased coin. Indeed, any oracle set X may be coded as a probability pX such that if a Turing machine is given a coin which lands heads with probability pX it can compute any function recursive in X with arbitrarily high probability. We also show (...) how the assumption of a non-recursive bias can be weakened by using a.. (shrink)

We refine the definition of II-computability of [12] so that oracles have a “consistent”, but natural, behaviour. We prove a Kleene Normal Form Theorem and closure of semi-recursive relations under ∃1. We also show that in this more inclusive computation theory Post's theorem in the arithmetical hierarchy still holds.

There has recently been work by multiple groups in extracting the properties associated with cardinal invariants of the continuum and translating these properties into similar analogous combinatorial properties of computational oracles. Each property yields a highness notion in the Turing degrees. In this paper we study the highness notions that result from the translation of the evasion number and its dual, the prediction number, as well as two versions of the rearrangement number. When translated appropriately, these yield four new highness (...) notions. We will define these new notions, show some of their basic properties and place them in the computability-theoretic version of Cichoń's diagram. (shrink)

This paper examines the role of power structures and strategic decisions in trajectories toward war and peace. Part I introduces a fuzzy inference engine for computationally simulating balance of power. Part II compares simulation results from hegemonic, bi-polar, and multi-polar system structures, each with three actors. Part III explores strategies for maximizing peace under each of these system structures. Part IV applies these lessons to real-world event chronologies.

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)

Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA (...) relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. (shrink)

Certain enterprises at the fringes of science, such as intelligent design creationism, claim to identify phenomena that go beyond not just our present physics but any possible physical explanation. Asking what it would take for such a claim to succeed, we introduce a version of physicalism that formulates the proposition that all available data sets are best explained by combinations of “chance and necessity”—algorithmic rules and randomness. Physicalism would then be violated by the existence of oracles that produce certain kinds (...) of noncomputable functions. Examining how a candidate for such an oracle would be evaluated leads to questions that do not admit an easy resolution. Since we lack any plausible candidate for any such oracle, however, chance-and-necessity physicalism appears very likely to be correct. (shrink)

We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be (...) “large” using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62 457–486] allows to derive from some short semantic derivations of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol computing the Karchmer–Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] from (...) [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity. In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle, that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63 1582–1596] ) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. (shrink)

Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain (...) similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields. (shrink)

Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Δn+10 basic sequence with respect to which no Δn0 real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.

The automation of many repetitive or dangerous human activities yields numerous advantages. In order to automate a physical task that requires a finite series of sequential steps, the translation of those steps in terms of a computational procedure is often required. Even apparently menial tasks like following a cooking recipe may involve complex operations that can’t be perfectly described in formal terms. Recently, several studies have explored the possibility to model cooking recipes as a computational procedure based on a set (...) of instructions. This vision is the foundation for the construction of robotics kitchen, as Moley. These kitchen robots have shown promising results. Moley, for instance, is the very first example of a new generation of bioinspired robotics, based on the reproduction of particular movement, cooking, through artificial arms and hands. It is entirely different from the current appliances present in our domestic domain because Moley is able to manipulate ingredients and interact with kitchen equipment in order to prepare a dish autonomously. Nonetheless, they have also shown several limitations. In particular, Moley is an entirely autonomous robot in a structured environment in which it knows precisely the object position and manipulates the ingredients based on a list of instructions and a training phase made by Machine Learning. In this contribution we contend that these limitations arise from an essential mismatch between computational procedures, as originally described by Turing in his seminal 1936 paper, and recipes. Computational procedures have been originally created to observe and modify formal symbols with formal operators. Thus, they are independent from time and they are ideally executed in a closed environment, in which the computer directly produces all the relevant changes required to produce the intended result. Recipes, instead, are followed in an open environment, in which, while time goes by, changes happen independently from the cook’s intervention: the cook puts the butter on the pan, starts the fire and then waits until the butter is melted. To operate effectively in the open environment a kitchen robot must couple computational procedures with sensors, e.g a sensor which provides a time signal. These sensors are de facto oracles for the procedures and yet are required to bridge the gap from the formal to the physical world. (shrink)

Alan M. Turing, pioneer of computing and WWII codebreaker, is one of the most important and influential thinkers of the twentieth century. In this volume for the first time his key writings are made available to a broad, non-specialist readership. They make fascinating reading both in their own right and for their historic significance: contemporary computational theory, cognitive science, artificial intelligence, and artificial life all spring from this ground-breaking work, which is also rich in philosophical and logical insight. An introduction (...) by leading Turing expert Jack Copeland provides the background and guides the reader through the selection. About Alan Turing Alan Turing FRS OBE, (1912-1954) studied mathematics at King's College, Cambridge. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. During 1936-1938 Turing continued his studies, now at Princeton University. He completed a PhD in mathematical logic, analysing the notion of 'intuition' in mathematics and introducing the idea of oracular computation, now fundamental in mathematical recursion theory. An 'oracle' is an abstract device able to solve mathematical problems too difficult for the universal Turing machine. In the summer of 1938 Turing returned to his Fellowship at King's. When WWII started in 1939 he joined the wartime headquarters of the Government Code and Cypher School (GC&CS) at Bletchley Park, Buckinghamshire. Building on earlier work by Polish cryptanalysts, Turing contributed crucially to the design of electro-mechanical machines ('bombes') used to decipher Enigma, the code by means of which the German armed forces sought to protect their radio communications. Turing's work on the version of Enigma used by the German navy was vital to the battle for supremacy in the North Atlantic. He also contributed to the attack on the cyphers known as 'Fish'. Based on binary teleprinter code, Fish was used during the latter part of the war in preference to morse-based Enigma for the encryption of high-level signals, for example messages from Hitler and other members of the German High Command. It is estimated that the work of GC&CS shortened the war in Europe by at least two years. Turing received the Order of the British Empire for the part he played. In 1945, the war over, Turing was recruited to the National Physical Laboratory (NPL) in London, his brief to design and develop an electronic computer - a concrete form of the universal Turing machine. Turing's report setting out his design for the Automatic Computing Engine (ACE) was the first relatively complete specification of an electronic stored-program general-purpose digital computer. Delays beyond Turing's control resulted in NPL's losing the race to build the world's first working electronic stored-program digital computer - an honour that went to the Royal Society Computing Machine Laboratory at Manchester University, in June 1948. Discouraged by the delays at NPL, Turing took up the Deputy Directorship of the Royal Society Computing Machine Laboratory in that year. Turing was a founding father of modern cognitive science and a leading early exponent of the hypothesis that the human brain is in large part a digital computing machine, theorising that the cortex at birth is an 'unorganised machine' which through 'training' becomes organised 'into a universal machine or something like it'. He also pioneered Artificial Intelligence. Turing spent the rest of his short career at Manchester University, being appointed to a specially created Readership in the Theory of Computing in May 1953. He was elected a Fellow of the Royal Society of London in March 1951 (a high honour). (shrink)

We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other complexity functions. In particular, $H^\infty$ (...) is different from $H^A$, the prefix-free complexity of monotone machines with oracle A. (shrink)

The usual representation of quantum algorithms, limited to the process of solving the problem, is physically incomplete. We complete it in three steps: extending the representation to the process of setting the problem, relativizing the extended representation to the problem solver to whom the problem setting must be concealed, and symmetrizing the relativized representation for time reversal to represent the reversibility of the underlying physical process. The third steps projects the input state of the representation, where the problem solver is (...) completely ignorant of the setting and thus the solution of the problem, on one where she knows half solution. Completing the physical representation shows that the number of computation steps required to solve any oracle problem in an optimal quantum way should be that of a classical algorithm endowed with the advanced knowledge of half solution. (shrink)

Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals.

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared (...) with the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

We obtain a large class of significant examples of n-random reals (i.e., Martin-Löf random in oracle $\varphi ^{(n - 1)} $ ) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set O ⊆(ℕ). In particular, we develop methods to transfer $\Sigma _n^0 $ or $\Pi _n^0 $ or many-one completeness results (...) of index sets to n-randomness of associated probabilities. (shrink)

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms (...) of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis. (shrink)

One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

Since its conception nearly 20 years ago, Logic Programming - the idea of using logic as a programming language - has been developed to the point where it now plays an important role in areas such as database theory, artificial intelligence and software engineering. However, there are still many challenging research issues to be addressed and the UK branch of the Association for Logic Programming was set up to provide a forum where the flourishing research community could discuss important issues (...) of Logic Programming which were often by-passed at the large international conferences. This volume contains the twelve papers which were presented at the ALPUK's 3rd conference which was held in Edinburgh, 10-12 April 1991. The aim of the conference was to give a broad but detailed technical insight into the work currently being done in this field, both in the UK and by researchers as far afield as Canada and Bulgaria. The breadth of interest in this area of Computer Science is reflected in the range of the papers which cover - amongst other areas - massively parallel implementation, constraint logic programming, circuit modelling, algebraic proof of program properties, deductive databases, specialised editors and standardisation. The resulting volume gives a good overview of the current progress being made in the field and will be of interest to researchers and students of any aspects of logic programming, parallel computing or database techniques and management. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents the state (...) of the art in the area. (shrink)

Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish.

With 500+ papers and 20+ books spanning many scientific disciplines, Mark Burgin has left an indelible mark and legacy for future explorers of human thought and information technology professionals. In this paper, I discuss his contribution to the evolution of machine intelligence using his general theory of information (GTI) based on my discussions with him and various papers I co-authored during the past eight years. His construction of a new class of digital automata to overcome the barrier posed by the (...) Church–Turing Thesis, and his contribution to super-symbolic computing with knowledge structures, cognizing oracles, and structural machines are leading to practical applications changing the future landscape of information systems. GTI provides a model for the operational knowledge of biological systems to build, operate, and manage life processes using 30+ trillion cells capable of replication and metabolism. The schema and associated operations derived from GTI are also used to model a digital genome specifying the operational knowledge of algorithms executing the software life processes with specific purposes using replication and metabolism. The result is a digital software system with a super-symbolic computing structure exhibiting autopoietic and cognitive behaviors that biological systems also exhibit. We discuss here one of these applications. (shrink)

The topics approached in the 52 papers included in this book are: neutrosophic sets; neutrosophic logic; generalized neutrosophic set; neutrosophic rough set; multigranulation neutrosophic rough set (MNRS); neutrosophic cubic sets; triangular fuzzy neutrosophic sets (TFNSs); probabilistic single-valued (interval) neutrosophic hesitant fuzzy set; neutro-homomorphism; neutrosophic computation; quantum computation; neutrosophic association rule; data mining; big data; oracle Turing machines; recursive enumerability; oracle computation; interval number; dependent degree; possibility degree; power aggregation operators; multi-criteria group decision-making (MCGDM); expert set; (...) soft sets; LA-semihypergroups; single valued trapezoidal neutrosophic number; inclusion relation; Q-linguistic neutrosophic variable set; vector similarity measure; fundamental neutro-homomorphism theorem; neutro-isomorphism theorem; quasi neutrosophic triplet loop; quasi neutrosophic triplet group; BE-algebra; cloud model; Maclaurin symmetric mean; pseudo-BCI algebra; hesitant fuzzy set; photovoltaic plan; decision-making trial and evaluation laboratory (DEMATEL); Choquet integral; fuzzy measure; clustering algorithm; and many more. (shrink)

The topics approached in this collection of papers are: neutrosophic sets; neutrosophic logic; generalized neutrosophic set; neutrosophic rough set; multigranulation neutrosophic rough set (MNRS); neutrosophic cubic sets; triangular fuzzy neutrosophic sets (TFNSs); probabilistic single-valued (interval) neutrosophic hesitant fuzzy set; neutro-homomorphism; neutrosophic computation; quantum computation; neutrosophic association rule; data mining; big data; oracle Turing machines; recursive enumerability; oracle computation; interval number; dependent degree; possibility degree; power aggregation operators; multi-criteria group decision-making (MCGDM); expert set; soft sets; LA-semihypergroups; (...) single valued trapezoidal neutrosophic number; inclusion relation; Q-linguistic neutrosophic variable set; vector similarity measure; fundamental neutro-homomorphism theorem; neutro-isomorphism theorem; quasi neutrosophic triplet loop; quasi neutrosophic triplet group; BE-algebra; cloud model; fuzzy measure; clustering algorithm; and many more. (shrink)

We study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates, $I\Delta_1$ . We show that $I\Delta_1$ is independent from the set of all true arithmetical $\Pi_2-sentences$ . Moreover, we establish the connections between this theory and some classes of oracle computable functions with restrictions on the allowed number of queries. We also obtain some conservation and independence results for parameter free and inference rule forms of $\Delta_1-induction$ . An open problem formulated by (...) J. Paris is whether $I\Delta_1$ proves the corresponding least element principle for decidable predicates, $L\Delta_1$ (or, equivalently. the $\Sigma_1-collection$ principle $B\Sigma_1$ ). We reduce this question to a purely computation-theoretic one. (shrink)

This note is a continuation of our former paper ''Complexity of the r-query tautologies in the presence of a generic oracle.'' We give a very short direct proof of the nonexistence of t-generic oracles, a result obtained first by Dowd. We also reconstitute a proof of Dowd's result that the class of all r-generic oracles in his sense has Lebesgue measure one.

We study the computational complexity of finding a line that bisects simultaneously two sets in the two-dimensional plane, called the pancake problem, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main results are: (1) The complexity of bisecting a nice (thick) polynomial-time approximable set at a given direction can be characterized by the counting class #P. (2) The complexity of bisecting simultaneously two linearly separable (...) nice (thick) polynomial-time approximable sets can be characterized by the counting class #P. (3) For either of these two problems, without the thickness condition and the linear separability condition (for the two-set case), it is arbitrarily hard to compute the bisector, even if it is unique. (shrink)