The Experts below are selected from a list of 6129 Experts worldwide ranked by ideXlab platform
Sam Sanders - One of the best experts on this subject based on the ideXlab platform.
-
open sets in Computability Theory and reverse mathematics
2020Co-Authors: Dag Normann, Sam SandersAbstract:To enable the study of open sets in computational approaches to mathematics, lots of extra data and structure on these sets is assumed. For both foundational and mathematical reasons, it is then a natural question, and the subject of this paper, what the influence of this extra data and structure is on the logical and computational properties of basic theorems pertaining to open sets. To answer this question, we study various basic theorems of analysis, like the Baire category, Heine, Heine-Borel, Urysohn, and Tietze theorems, all for open sets given by their (third-order) characteristic functions. Regarding Computability Theory, the objects claimed to exist by the aforementioned theorems undergo a shift from `computable' to `not computable in any type two functional', following Kleene's S1-S9. Regarding Reverse Mathematics, the latter's so-called Main Question, namely which set existence axioms are necessary for proving a given theorem, does not have a unique or unambiguous answer for the aforementioned theorems, working in Kohlenbach's higher-order framework. A finer study of representations of open sets leads to the new `$\Delta$-functional' which has unique (computational) properties.
-
the axiom of choice in Computability Theory and reverse mathematics with a cameo for the continuum hypothesis
2020Co-Authors: Dag Normann, Sam SandersAbstract:The Axiom of Choice (AC for short) is the most (in)famous axiom of the usual foundations of mathematics, ZFC set Theory. The (non-)essential use of AC in mathematics has been well-studied and thoroughly classified. Now, fragments of countable AC not provable in ZF have recently been used in Kohlenbach's higher-order Reverse Mathematics to obtain equivalences between closely related compactness and local-global principles. We continue this study and show that NCC, a weak choice principle provable in ZF and much weaker systems, suffices for many of these results. In light of the intimate connection between Reverse Mathematics and Computability Theory, we also study realisers for NCC, i.e. functionals that produce the choice functions claimed to exist by the latter from the other data. Our hubris of undertaking the hitherto underdeveloped study of the computational properties of (choice functions from) AC leads to interesting results. For instance, using Kleene's S1-S9 computation schemes, we show that various total realisers for NCC compute Kleene's $\exists^3$, a functional that gives rise to full second-order arithmetic, and vice versa. By contrast, partial realisers for NCC should be much weaker, but establishing this conjecture remains elusive. By way of catharsis, we show that the Continuum Hypothesis (CH for short) is equivalent to the existence of a countably based partial realiser for NCC. The latter kind of realiser does not compute Kleene's $\exists^3$ and is therefore strictly weaker than a total one.
-
Computability Theory nonstandard analysis and their connections
2019Co-Authors: Dag Normann, Sam SandersAbstract:We investigate the connections between Computability Theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related.(T.1) A basic property of Cantor space.(T.2) A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.Our study of (T.1) yields exotic objects in Computability Theory, while (T.2) leads to surprising results in Reverse Mathematics. We stress that (T.1) and (T.2) are highly intertwined, i.e., our study is holistic in nature in that results in Computability Theory yield results in Nonstandard Analysis and vice versa.
-
the strength of compactness in Computability Theory and nonstandard analysis
2019Co-Authors: Dag Normann, Sam SandersAbstract:Abstract Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space 2 N for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of 2 N ? Another natural question is: how hard is it to compute a sequence that covers 2 N minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, transfinite recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely Π 2 1 - CA 0 ), and even into Schweber's higher-order framework (namely Σ 1 2 -separation).
-
reverse mathematics and Computability Theory of domain Theory
2019Co-Authors: Sam SandersAbstract:This paper deals with the foundations of mathematics and computer science, domain Theory in particular; the latter studies certain ordered sets, called domains, with close relations to topology. Conceptually speaking, domain Theory provides a highly abstract and general formalisation of the intuitive notions ‘approximation’ and ‘convergence’. Thus, a major application in computer science is the semantics of programming languages. We study the following foundational questions: (Q1) Which axioms are needed to prove basic results in domain Theory? (Q2) How hard it is to compute the objects in these basic results?
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
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.
-
Computability Theory and differential geometry
2004Co-Authors: Robert I. SoareAbstract:Let $M$ be a smooth, compact manifold of dimension $n\geq 5$ and sectional curvature $ |K| \leq 1$. Let Met($M$) = Riem($M$)/Diff($M$) be the space of Riemannian metrics on $M$ modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met($M$) such as the diameter. They showed that for every Turing machine $T_e, e \in \omega$, there is a sequence (uniformly effective in $e$) of homology n-spheres {$P_k^e$}$_ k\in\omega$ which are also hypersurfaces, such that $P_k^e$ is diffeomorphic to the standard $n$-sphere $S^n$(denoted $P_k^e \approx_{\rm{diff}} S^n$ iff $T_e$ halts on input k, and in this case the connected sum $N_k^e = M \# P_k^e \approx_{\rm{diff}}M$, so $N_k^e \in $Met($M$), and $N_k^e$ is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time $\sigma_e(k)$ of $T_e$ on inputs $y
-
applications of Computability Theory to prime models and differential geometry
2003Co-Authors: Robert I. Soare, Barbara F CsimaAbstract:We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic Theory has a prime model whose elementary diagram is low. If we have a complete decidable atomic Theory with all types of the Theory computable, we show that for every degree d with 0 < d ≤ 0′, there is a prime model with elementary diagram of degree d. We say that a set X is prime bounding if for every complete decidable atomic Theory T there is a prime model U of T decidable in X. In joint work with Denis Hirschfeldt, Julia Knight, and Robert Soare, we give the characterization that the prime bounding sets X ≤T ∅ ′ are exactly the sets which are not low2. Recent results of Alex Nabutovsky and Schmuel Weinberger in differential geometry have required the construction by Robert Soare of a certain sequence of computably enumerable sets. Weinberger later asked for a stronger sequence, which we construct. In addition, he introduced an ordering with geometric applications and asked for its Computability theoretic properties, which we study.
-
Computability and Recursion
1996Co-Authors: Robert I. SoareAbstract:We consider the informal concept of "Computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) Computability" and "(general) recursiveness." We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of Computability Theory, and its connection to other related areas
Sanders Sam - One of the best experts on this subject based on the ideXlab platform.
-
Open sets in Computability Theory and Reverse Mathematics
2020Co-Authors: Normann Dag, Sanders SamAbstract:To enable the study of open sets in computational approaches to mathematics, lots of extra data and structure on these sets is assumed. For both foundational and mathematical reasons, it is then a natural question, and the subject of this paper, what the influence of this extra data and structure is on the logical and computational properties of basic theorems pertaining to open sets. To answer this question, we study various basic theorems of analysis, like the Baire category, Heine, Heine-Borel, Urysohn, and Tietze theorems, all for open sets given by their (third-order) characteristic functions. Regarding Computability Theory, the objects claimed to exist by the aforementioned theorems undergo a shift from `computable' to `not computable in any type two functional', following Kleene's S1-S9. Regarding Reverse Mathematics, the latter's so-called Main Question, namely which set existence axioms are necessary for proving a given theorem, does not have a unique or unambiguous answer for the aforementioned theorems, working in Kohlenbach's higher-order framework. A finer study of representations of open sets leads to the new `$\Delta$-functional' which has unique (computational) properties.Comment: 40 pages, to appear in Journal of Logic and Computation, Special Issue on Logical Foundations of Computer Science (LFCS2020
-
The Axiom of Choice in Computability Theory and Reverse Mathematics, with a cameo for the Continuum Hypothesis
2020Co-Authors: Normann Dag, Sanders SamAbstract:The Axiom of Choice (AC for short) is the most (in)famous axiom of the usual foundations of mathematics, ZFC set Theory. The (non-)essential use of AC in mathematics has been well-studied and thoroughly classified. Now, fragments of countable AC not provable in ZF have recently been used in Kohlenbach's higher-order Reverse Mathematics to obtain equivalences between closely related compactness and local-global principles. We continue this study and show that NCC, a weak choice principle provable in ZF and much weaker systems, suffices for many of these results. In light of the intimate connection between Reverse Mathematics and Computability Theory, we also study realisers for NCC, i.e. functionals that produce the choice functions claimed to exist by the latter from the other data. Our hubris of undertaking the hitherto underdeveloped study of the computational properties of (choice functions from) AC leads to interesting results. For instance, using Kleene's S1-S9 computation schemes, we show that various total realisers for NCC compute Kleene's $\exists^3$, a functional that gives rise to full second-order arithmetic, and vice versa. By contrast, partial realisers for NCC should be much weaker, but establishing this conjecture remains elusive. By way of catharsis, we show that the Continuum Hypothesis (CH for short) is equivalent to the existence of a countably based partial realiser for NCC. The latter kind of realiser does not compute Kleene's $\exists^3$ and is therefore strictly weaker than a total one.Comment: 25 pages, to appear in Journal for Logic and Computation (2021). The 'preliminaries' in Section 2 can also be found in most of our other papers like arXiv:1910.0248
-
The Axiom of Choice in Computability Theory and Reverse Mathematics, with a cameo for the Continuum Hypothesis
2020Co-Authors: Normann Dag, Sanders SamAbstract:The Axiom of Choice (AC for short) is the most (in)famous axiom of the usual foundations of mathematics, ZFC set Theory. The (non-)essential use of AC in mathematics has been well-studied and thoroughly classified. Now, fragments of countable AC not provable in ZF have recently been used in Kohlenbach's higher-order Reverse Mathematics to obtain equivalences between closely related compactness and local-global principles. We continue this study and show that NCC, a weak choice principle provable in ZF and much weaker systems, suffices for many of these results. In light of the intimate connection between Reverse Mathematics and Computability Theory, we also study realisers for NCC, i.e. functionals that produce the choice functions claimed to exist by the latter from the other data. Our hubris of undertaking the hitherto underdeveloped study of the computational properties of (choice functions from) AC leads to interesting results. For instance, using Kleene's S1-S9 computation schemes, we show that various total realisers for NCC compute Kleene's $\exists^3$, a functional that gives rise to full second-order arithmetic, and vice versa. By contrast, partial realisers for NCC should be much weaker, but establishing this conjecture remains elusive. By way of catharsis, we show that the Continuum Hypothesis (CH for short) is equivalent to the existence of a countably based partial realiser for NCC. The latter kind of realiser does not compute Kleene's $\exists^3$ and is therefore strictly weaker than a total one.Comment: 25 pages, The 'preliminaries' in Section 2 can also be found in most of our other papers. arXiv admin note: text overlap with arXiv:1910.0248
-
Pincherle's theorem in Reverse Mathematics and Computability Theory
2020Co-Authors: Normann Dag, Sanders SamAbstract:We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first 'local-to-global' principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindel\"of lemma.Comment: 43 pages, one appendix, to appear in Annals of Pure and Applied Logi
-
Pincherle's theorem in reverse mathematics and Computability Theory
2020Co-Authors: Normann Dag, Sanders SamAbstract:We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindelöf lemma
Dag Normann - One of the best experts on this subject based on the ideXlab platform.
-
open sets in Computability Theory and reverse mathematics
2020Co-Authors: Dag Normann, Sam SandersAbstract:To enable the study of open sets in computational approaches to mathematics, lots of extra data and structure on these sets is assumed. For both foundational and mathematical reasons, it is then a natural question, and the subject of this paper, what the influence of this extra data and structure is on the logical and computational properties of basic theorems pertaining to open sets. To answer this question, we study various basic theorems of analysis, like the Baire category, Heine, Heine-Borel, Urysohn, and Tietze theorems, all for open sets given by their (third-order) characteristic functions. Regarding Computability Theory, the objects claimed to exist by the aforementioned theorems undergo a shift from `computable' to `not computable in any type two functional', following Kleene's S1-S9. Regarding Reverse Mathematics, the latter's so-called Main Question, namely which set existence axioms are necessary for proving a given theorem, does not have a unique or unambiguous answer for the aforementioned theorems, working in Kohlenbach's higher-order framework. A finer study of representations of open sets leads to the new `$\Delta$-functional' which has unique (computational) properties.
-
the axiom of choice in Computability Theory and reverse mathematics with a cameo for the continuum hypothesis
2020Co-Authors: Dag Normann, Sam SandersAbstract:The Axiom of Choice (AC for short) is the most (in)famous axiom of the usual foundations of mathematics, ZFC set Theory. The (non-)essential use of AC in mathematics has been well-studied and thoroughly classified. Now, fragments of countable AC not provable in ZF have recently been used in Kohlenbach's higher-order Reverse Mathematics to obtain equivalences between closely related compactness and local-global principles. We continue this study and show that NCC, a weak choice principle provable in ZF and much weaker systems, suffices for many of these results. In light of the intimate connection between Reverse Mathematics and Computability Theory, we also study realisers for NCC, i.e. functionals that produce the choice functions claimed to exist by the latter from the other data. Our hubris of undertaking the hitherto underdeveloped study of the computational properties of (choice functions from) AC leads to interesting results. For instance, using Kleene's S1-S9 computation schemes, we show that various total realisers for NCC compute Kleene's $\exists^3$, a functional that gives rise to full second-order arithmetic, and vice versa. By contrast, partial realisers for NCC should be much weaker, but establishing this conjecture remains elusive. By way of catharsis, we show that the Continuum Hypothesis (CH for short) is equivalent to the existence of a countably based partial realiser for NCC. The latter kind of realiser does not compute Kleene's $\exists^3$ and is therefore strictly weaker than a total one.
-
Computability Theory nonstandard analysis and their connections
2019Co-Authors: Dag Normann, Sam SandersAbstract:We investigate the connections between Computability Theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related.(T.1) A basic property of Cantor space.(T.2) A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.Our study of (T.1) yields exotic objects in Computability Theory, while (T.2) leads to surprising results in Reverse Mathematics. We stress that (T.1) and (T.2) are highly intertwined, i.e., our study is holistic in nature in that results in Computability Theory yield results in Nonstandard Analysis and vice versa.
-
the strength of compactness in Computability Theory and nonstandard analysis
2019Co-Authors: Dag Normann, Sam SandersAbstract:Abstract Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space 2 N for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of 2 N ? Another natural question is: how hard is it to compute a sequence that covers 2 N minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, transfinite recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely Π 2 1 - CA 0 ), and even into Schweber's higher-order framework (namely Σ 1 2 -separation).
-
the strength of compactness in Computability Theory and nonstandard analysis
2018Co-Authors: Dag Normann, Sam SandersAbstract:The authors recently pioneered a connection between Nonstandard Analysis and Computability Theory, resulting in a number of surprising results and even more open questions. We answer some of the latter in this paper, all of which pertain to the two following intimately related topics. (T.1) A basic property of Cantor space $2^{\mathbb{N}}$ is Heine-Borel compactness: Any open cover of $2^{\mathbb{N}}$, has a finite sub-cover. A natural question is: How hard is it to compute such a finite sub-cover? We make this precise by analysing functionals that given $g:2^{\mathbb{N}}\rightarrow \mathbb{N}$, output $\langle f_0 , \dots, f_n\rangle $ in $2^{\mathbb{N}}$ such that the neighbourhoods defined from $\overline{f_i}g(f_i)$ for $i\leq n$ cover $2^{\mathbb{N}}$. The special and weak fan functionals are central objects in this study. (T.2) A basic property of $2^{\mathbb{N}}$ in Nonstandard Analysis is Abraham Robinson's nonstandard compactness, i.e. that every binary sequence is `infinitely close' to a standard binary sequence. We analyse the strength of this nonstandard compactness property in the spirit of Reverse Mathematics, which turns out to be intimately related to the computational properties of the special and weak fan functionals. We establish the connection between these new fan functionals on one hand, and arithmetical comprehension, transfinite recursion, and the Suslin functional on the other hand. We show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely $\Pi_2^1$-CA$_0$), and even into Schweber's higher-order framework (namely $\Sigma_{1}^{2}$-separation).
Iyad Rahwan - One of the best experts on this subject based on the ideXlab platform.
-
superintelligence cannot be contained lessons from Computability Theory
2021Co-Authors: Manuel Alfonseca, Manuel Cebrian, Antonio Fernandez Anta, Lorenzo Coviello, Andres Abeliuk, Iyad RahwanAbstract:Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potentially catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that total containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) impossible.
-
superintelligence cannot be contained lessons from Computability Theory
2016Co-Authors: Manuel Alfonseca, Manuel Cebrian, Antonio Fernandez Anta, Lorenzo Coviello, Andres Abeliuk, Iyad RahwanAbstract:Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potential catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that such containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) infeasible.