The Experts below are selected from a list of 648 Experts worldwide ranked by ideXlab platform
Martin Ziegler - One of the best experts on this subject based on the ideXlab platform.
-
1 Relative Computability and uniform continuity of relations
2013Co-Authors: Arno Pauly, Martin ZieglerAbstract:Abstract: A type-2 computable real function is necessarily continuous; and this remains true for computations Relative to any oracle. Conversely, by the Weierstrass Approximation Theorem, every continuous f: [0; 1] → R is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multi-valued functions f: [0; 1] ⇒ R (also known as multi-functions or relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y ∈ f (x), new ways arise of (linearly) ordering quantifiers—yet none turns out as satisfactory. We are thus led to a concept of uniform continuity based on the Henkin quantifier; and prove it necessary for Relative Computability of compact real relations. In fact iterating this condition yields a strict hierarchy of notions each necessary — and the ω-th level also sufficient — for Relative Computability. A refined, quantitative analysis exhibits a similar topological characterization of Relative polynomial-time Computability
-
Relative Computability and uniform continuity of relations
Journal of Logic and Analysis, 2013Co-Authors: Arno Pauly, Martin ZieglerAbstract:A type-2 computable real function is necessarily continuous; and this remains true for Relative, i.e. oracle-based, computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f :[0,1]→ℝ is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multi- valued functions f :[0,1]⇒ℝ (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y ∈ f ( x ), new ways arise of (linearly) ordering quantifiers — yet none turns out as satisfactory. We are thus led to a concept of uniform continuity based on the Henkin quantifier ; and prove it necessary for Relative Computability of compact real relations. In fact iterating this condition yields a strict hierarchy of notions each necessary — and the ω-th level also sufficient — for Relative Computability.
-
Relative Computability and uniform continuity of relations
arXiv: Logic, 2011Co-Authors: Arno Pauly, Martin ZieglerAbstract:A type-2 computable real function is necessarily continuous; and this remains true for Relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for Relative Computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for Relative Computability.
Richard A. Shore - One of the best experts on this subject based on the ideXlab platform.
-
Reverse mathematics, countable and uncountable: a computational approach
2010Co-Authors: Richard A. ShoreAbstract:Reverse mathematics analyzes the complexity of mathematical statements in terms of the strength of axiomatic systems needed to prove them. Its setting is countable mathematics and subsystems of second order arithmetic. We present a similar analysis based on (recursion theoretic) computational complexity instead. In the countable case, this view is implicit in many of results in the area. By making it explicit and precise, we provide an alternate approach to this type of analysis for countable mathematics. It may be more intelligible to some mathematicians in that it replaces logic and proof systems with Relative Computability. In the uncountable case, second order arithmetic and its proof theory is insu ¢ cient for the desired analysis. Our computational approach, however, supplies a ready made paradigm for similar analyses. It can be implemented with any appropriate notion of computation on uncountable sets.
-
Defining the Turing Jump
1999Co-Authors: Richard A. Shore, Theodore A. SlamanAbstract:Introduction The primary notion of eective Computability is that provided by Turing machines (or equivalently any of the other common models of computation). We denote the partial function computed by the eth Turing machine in some standard list by ' e . When these machines are equipped with an \oracle" for a subset A of the natural numbers !, i.e. an external procedure that answers questions of the form \is n in A", they dene the basic notion of Relative Computability or Turing reducibility (from Turing (1939)). We say that A is computable from (or recursive in) B if there is a Turing machine which, when equipped with an oracle for B, computes (the characteristic function of) A, i.e. for some e, ' B e = A. We denote this relation by A <F
-
Jumps of minimal degrees below 0
1996Co-Authors: Rodney G Downey, Richard A. ShoreAbstract:Abstract. We show that there is a degree a REA in and low over 0 ′ such that no minimal degree below 0 ′ jumps to a degree above a. We also show that every nonlow r.e. degree bounds a nonlow minimal degree. Introduction. An important and long-standing area of investigation in recursion theory has been the relationship between quantifier complexity of the definitions of sets in arithmetic as expressed by the jump operator and the basic notion of Relative Computability as expressed by the ordering of the (Turing) degrees. In this paper w
-
Jumps Of Minimal Degrees Below 0
1996Co-Authors: Rodney G Downey, Steffen Lempp, Richard A. ShoreAbstract:. We show that there is a degree a REA in and low over 0 0 such that no minimal degree below 0 0 jumps to a degree above a. We also show that every nonlow r.e. degree bounds a nonlow minimal degree. Introduction. An important and long-standing area of investigation in recursion theory has been the relationship between quantifier complexity of the definitions of sets in arithmetic as expressed by the jump operator and the basic notion of Relative Computability as expressed by the ordering of the (Turing) degrees. In this paper we are concerned with an aspect of the general problem of characterizing the range of the jump operator on various classes of degrees. The first such result was the completeness or jump inversion theorem of Friedberg [1957]. Theorem (Friedberg Jump Inversion). If c 0 0 then there is an a such that a 0 = c. As a 0 is obviously at least 0 0 for every degree a, this result says that every "possible" degree c (i.e., every degree not ruled out on trivi..
Miller Russell - One of the best experts on this subject based on the ideXlab platform.
-
Noncomputable Functions in the Blub-Shub-Smale Model
CUNY Academic Works, 2011Co-Authors: Calvert Wesley, Kramer Ken, Miller RussellAbstract:Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on Relative Computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for Relative BSS-Computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine
-
Noncomputable functions in the Blum-Shub-Smale model
'Logical Methods in Computer Science e.V.', 2011Co-Authors: Calvert Wesley, Kramer Ken, Miller RussellAbstract:Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on Relative Computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for Relative BSS-Computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine
Arno Pauly - One of the best experts on this subject based on the ideXlab platform.
-
1 Relative Computability and uniform continuity of relations
2013Co-Authors: Arno Pauly, Martin ZieglerAbstract:Abstract: A type-2 computable real function is necessarily continuous; and this remains true for computations Relative to any oracle. Conversely, by the Weierstrass Approximation Theorem, every continuous f: [0; 1] → R is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multi-valued functions f: [0; 1] ⇒ R (also known as multi-functions or relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y ∈ f (x), new ways arise of (linearly) ordering quantifiers—yet none turns out as satisfactory. We are thus led to a concept of uniform continuity based on the Henkin quantifier; and prove it necessary for Relative Computability of compact real relations. In fact iterating this condition yields a strict hierarchy of notions each necessary — and the ω-th level also sufficient — for Relative Computability. A refined, quantitative analysis exhibits a similar topological characterization of Relative polynomial-time Computability
-
Relative Computability and uniform continuity of relations
Journal of Logic and Analysis, 2013Co-Authors: Arno Pauly, Martin ZieglerAbstract:A type-2 computable real function is necessarily continuous; and this remains true for Relative, i.e. oracle-based, computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f :[0,1]→ℝ is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multi- valued functions f :[0,1]⇒ℝ (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y ∈ f ( x ), new ways arise of (linearly) ordering quantifiers — yet none turns out as satisfactory. We are thus led to a concept of uniform continuity based on the Henkin quantifier ; and prove it necessary for Relative Computability of compact real relations. In fact iterating this condition yields a strict hierarchy of notions each necessary — and the ω-th level also sufficient — for Relative Computability.
-
Relative Computability and uniform continuity of relations
arXiv: Logic, 2011Co-Authors: Arno Pauly, Martin ZieglerAbstract:A type-2 computable real function is necessarily continuous; and this remains true for Relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable Relative to some oracle. In their search for a similar topological characterization of Relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than Relative Computability) and strong continuity (which is stronger than Relative Computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for Relative Computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for Relative Computability.
Robert I. Soare - One of the best experts on this subject based on the ideXlab platform.
-
Turing Computability: Theory and Applications
2016Co-Authors: Robert I. SoareAbstract:Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to Computability theory, the study of what machines can and cannot compute. This book presents classical Computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all mathematicians recognize in their subject. Part I gives a thorough development of the foundations of Computability, from the definition of Turing machines up to finite injury priority arguments. Key topics include Relative Computability, and computably enumerable sets, those which can be effectively listed but not necessarily effectively decided, such as the theorems of Peano arithmetic. Part II includes the study of computably open and closed sets of reals and basis and nonbasis theorems for effectively closed sets. Part III covers minimal Turing degrees. Part IV is an introduction to games and their use in proving theorems. Finally, Part V offers a short history of Computability theory. The author has honed the content over decades according to feedback from students, lecturers, and researchers around the world. Most chapters include exercises, and the material is carefully structured according to importance and difficulty. The book is suitable for advanced undergraduate and graduate students in computer science and mathematics and researchers engaged with Computability and mathematical logic.
-
turing oracle machines online computing and three displacements in Computability theory
Annals of Pure and Applied Logic, 2009Co-Authors: Robert I. SoareAbstract:We begin with the history of the discovery of Computability in the 1930’s, the roles of Godel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Godel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-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.
-
Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
1996Co-Authors: Leo Harrington, Robert I. SoareAbstract:We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them Relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to Relative Computability (Turing reducibility)
-
Definability, Automorphisms, And Dynamic Properties Of Computably Enumerable Sets
1996Co-Authors: Leo Harrington, Robert I. SoareAbstract:. We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them Relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to Relative Computability (Turing reducibility). 1. Introduction. All functions are on the nonnegative integers, # = {0, 1, 2, . . . }, and all sets will be subsets of #. Turing and G odel informally called a function computable if it can be calculated by a mechanical procedure, and regarded this as being synonymous with being specified by an "algorithm" or a "finite combinatorial procedure." They each formalized it as follows. 1 A function is Turing computable if it is definable by a Turing machine, as defined by Turing ..