The Experts below are selected from a list of 315 Experts worldwide ranked by ideXlab platform
Pascal Vanier - One of the best experts on this subject based on the ideXlab platform.
-
Undecidable word problem in subshift automorphism groups
2019Co-Authors: Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, Pascal VanierAbstract:This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing Degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly this Degree.
-
Turing Degree spectra of minimal subshifts
Computer Science Symposium in Russia, 2017Co-Authors: Michael Hochman, Pascal VanierAbstract:Subshifts are shift invariant closed subsets of \(\varSigma ^{\mathbb {Z}^d}\), with \(\varSigma \) a finite alphabet. Minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing Degree spectra of non-periodic minimal subshifts always contain the cone of Turing Degrees above any of its Degrees. It was however not known whether each minimal subshift’s spectrum was formed of exactly one cone or not. We construct inductively a minimal subshift whose spectrum consists of an uncountable number of cones with incomparable bases.
-
CSR - Turing Degree Spectra of Minimal Subshifts
Computer Science – Theory and Applications, 2017Co-Authors: Michael Hochman, Pascal VanierAbstract:Subshifts are shift invariant closed subsets of \(\varSigma ^{\mathbb {Z}^d}\), with \(\varSigma \) a finite alphabet. Minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing Degree spectra of non-periodic minimal subshifts always contain the cone of Turing Degrees above any of its Degrees. It was however not known whether each minimal subshift’s spectrum was formed of exactly one cone or not. We construct inductively a minimal subshift whose spectrum consists of an uncountable number of cones with incomparable bases.
-
Turing Degree spectra of minimal subshifts
arXiv: Formal Languages and Automata Theory, 2014Co-Authors: Michael Hochman, Pascal VanierAbstract:Subshifts are shift invariant closed subsets of $\Sigma^{\mathbb{Z}^d}$ , minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing Degree spectra of non-periodic minimal subshifts always contain the cone of Turing Degrees above any of its Degree. It was however not known whether each minimal subshift's spectrum was formed of exactly one cone or not. We construct inductively a minimal subshift whose spectrum consists of an uncountable number of cones with disjoint base.
-
A note on Turing Degree spectra of minimal subshifts.
arXiv: Formal Languages and Automata Theory, 2014Co-Authors: Michael Hochman, Pascal VanierAbstract:Subshifts are shift invariant closed subsets of $\Sigma^{\mathbb{Z}^d}$, minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing Degree spectra of non-periodic minimal subshifts always contain the cone of Turing Degrees above any of its Degree. It was however not known whether each minimal subshift's spectrum was formed of exactly one cone or not. We construct inductively a minimal subshift whose spectrum consists of an uncountable number of cones with disjoint base.
Frank Stephan - One of the best experts on this subject based on the ideXlab platform.
-
Depth, Highness and DNR Degrees
2015Co-Authors: Philippe Moser, Frank StephanAbstract:We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deep K , O(1)-deep C , order-deep K and order-deep C sequences. Our main results are that Martin-Löf random sets are not order-deep C , that every many-one Degree contains a set which is not O(1)-deep C , that O(1)-deep C sets and order-deep K sets have high or DNR Turing Degree and that no K-trival set is O(1)-deep K .
-
Index sets and universal numberings
Journal of Computer and System Sciences, 2011Co-Authors: Sanjay Jain, Frank Stephan, Jason TeutschAbstract:This paper studies the Turing Degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN^@? of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN^@? is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing Degree.
-
Constructive Dimension and Turing Degrees
Theory of Computing Systems, 2009Co-Authors: Laurent Bienvenu, David Doty, Frank StephanAbstract:This paper examines the constructive Hausdorff and packing dimensions of Turing Degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim _H( S ) and constructive packing dimension dim _P( S ) is Turing equivalent to a sequence R with dim _H( R )≥(dim _H( S )/dim _P( S ))− ε , for arbitrary ε >0. Furthermore, if dim _P( S )>0, then dim _P( R )≥1− ε . The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S , as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing Degrees. A lower bound of dim _H( S )/dim _P( S ) is shown to hold for the Turing Degree of any sequence S . A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing Degrees. It is also shown that, for any regular sequence S (that is, dim _H( S )=dim _P( S )) such that dim _H( S )>0, the Turing Degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.
-
Constructive Dimension and Turing Degrees
Theory of Computing Systems, 2009Co-Authors: Laurent Bienvenu, David Doty, Frank StephanAbstract:This paper examines the constructive Hausdorff and packing dimensions of Turing Degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim H(S) and constructive packing dimension dim P(S) is Turing equivalent to a sequence R with dim H(R)≥(dim H(S)/dim P(S))−e, for arbitrary e>0. Furthermore, if dim P(S)>0, then dim P(R)≥1−e. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing Degrees. A lower bound of dim H(S)/dim P(S) is shown to hold for the Turing Degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing Degrees. It is also shown that, for any regular sequence S (that is, dim H(S)=dim P(S)) such that dim H(S)>0, the Turing Degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.
-
CiE - Index Sets and Universal Numberings
Mathematical Theory and Computational Practice, 2009Co-Authors: Sanjay Jain, Frank Stephan, Jason TeutschAbstract:This paper studies the Turing Degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN* of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing Degree.
George Barmpalias - One of the best experts on this subject based on the ideXlab platform.
-
Random numbers as probabilities of machine behaviour
arXiv: Computational Complexity, 2016Co-Authors: George Barmpalias, Douglas Cenzer, Christopher P. PorterAbstract:A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. For example, Chaitin's Omega is a well known Martin-Loef random number that is obtained by considering the halting probability of a universal prefix-free machine. In the last decade, similar examples have been obtained for higher forms of randomness, i.e. randomness relative to strong oracles. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to different machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing Degree when they are defined with respect to different universal machines.
-
The typical Turing Degree
Proceedings of the London Mathematical Society, 2013Co-Authors: George Barmpalias, Adam R. Day, Andy Lewis-pyeAbstract:The Turing Degree of a real measures the computational difficulty of producing its binary expansion. Since Turing Degrees are tailsets, it follows from Kolmogorov’s 0-1 law that for any property which may or may not be satisfied by any given Turing Degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the typical Degree satisfies the property, or else the typical Degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. A similar analysis can be made in terms of Baire category, where a standard form of genericity now plays the role that randomness plays in the context of measure. We describe and prove a number of results in a programme of research which aims to establish the properties of the typical Turing Degree, where typicality is gauged either in terms of Lebesgue measure or Baire category.
-
The typical Turing Degree
arXiv: Logic, 2011Co-Authors: George Barmpalias, Adam R. Day, Andrew E. M. LewisAbstract:The Turing Degree of a real measures the computational difficulty of producing its binary expansion. Since Turing Degrees are tailsets, it follows from Kolmogorov's 0-1 law that for any property which may or may not be satisfied by any given Turing Degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the \emph{typical} Degree satisfies the property, or else the typical Degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. A similar analysis can be made in terms of Baire category, where a standard form of genericity now plays the role that randomness plays in the context of measure. We describe and prove a number of results in a programme of research which aims to establish the properties of the typical Turing Degree, where typicality is gauged either in terms of Lebesgue measure or Baire category.
Valentina S. Harizanov - One of the best experts on this subject based on the ideXlab platform.
-
CiE - Automorphism Groups of Substructure Lattices of Vector Spaces in Computable Algebra
Pursuit of the Universal, 2016Co-Authors: Rumen D. Dimitrov, Valentina S. Harizanov, Andrei S. MorozovAbstract:For a Turing Degree \(\mathbf {x}\), we investigate the automorphisms of the lattice of \(\mathbf {x}\)-c.e. vector spaces. We establish the equivalence of the embedding relation for these automorphism groups with the order relation on the corresponding Turing Degrees. By a result of Guichard the automorphisms of the lattice of \(\mathbf {x}\)-c.e. vector spaces are induced by \(\mathbf {x}\)-computable invertible semilinear transformations, GSL\(_{\mathbf {x}}\). We prove that the Turing Degree spectrum of the group GSL\(_{\mathbf {x}}\) is the upper cone of Turing Degrees \(\ge \mathbf {x}^{\prime \prime }\).
-
Turing Degrees of Isomorphism Types of Geometric Objects
Computability, 2014Co-Authors: Wesley Calvert, Valentina S. Harizanov, Alexandra ShlapentokhAbstract:We initiate the computability-theoretic study of ringed spaces and schemes. In particular, we show that any Turing Degree may occur as the least Degree of an isomorphic copy of a structure of these kinds. We also show that these structures may fail to have a least Degree.
-
Spaces of orders and their Turing Degree spectra
Annals of Pure and Applied Logic, 2010Co-Authors: Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, Valentina S. Harizanov, Amir A. ToghaAbstract:Abstract We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G , which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing Degree spectra contain certain upper cones of Degrees. Our approach unifies and extends Sikora’s (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F n of rank n > 1 has a bi-order in every Turing Degree.
-
Turing Degrees of nonabelian groups
Proceedings of the American Mathematical Society, 2007Co-Authors: Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, Valentina S. Harizanov, A. S. SikoraAbstract:For a countable structure A, the (Turing) Degree spectrum of A is the set of all Turing Degrees of its isomorphic copies. If the Degree spectrum of A has the least Degree d, then we say that d is the (Turing) Degree of the isomorphism type of A. So far, Degrees of the isomorphism types have been studied for abelian and metabelian groups. Here, we focus on highly nonabelian groups. We show that there are various centerless groups whose isomorphism types have arbitrary Turing Degrees. We also show that there are various centerless groups whose isomorphism types do not have Turing Degrees.
-
Turing Degrees of isomorphism types of algebraic objects
Journal of the London Mathematical Society, 2007Co-Authors: Wesley Calvert, Valentina S. Harizanov, Alexandra ShlapentokhAbstract:The Turing Degree spectrum of a countable structure A is the set of all Turing Degrees of isomorphic copies of A. The Turing Degree of the isomorphism type of A, if it exists, is the least Turing Degree in its Degree spectrum. We show that there are elements with isomorphism types of arbitrary Turing Degrees in each of the following classes: countable fields, rings, and torsion-free Abelian groups of any finite rank. We also show that there are structures in each of these classes the isomorphism types of which do not have Turing Degrees. The case of torsion-free Abelian groups of finite rank settles a question left open by Knight, Downey and Jockusch [Downey, Complexity, logic, and recursion theory, Lecture Notes in Pure and Applied Mathematics 187 (ed. A. Sorbi; Marcel Dekker, New York, 1997) 157–205].
Christopher P. Porter - One of the best experts on this subject based on the ideXlab platform.
-
Random numbers as probabilities of machine behavior
Theoretical Computer Science, 2017Co-Authors: Christopher P. PorterAbstract:Abstract A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behavior of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to several machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing Degree when they are defined with respect to different universal machines.
-
Random numbers as probabilities of machine behaviour
arXiv: Computational Complexity, 2016Co-Authors: George Barmpalias, Douglas Cenzer, Christopher P. PorterAbstract:A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. For example, Chaitin's Omega is a well known Martin-Loef random number that is obtained by considering the halting probability of a universal prefix-free machine. In the last decade, similar examples have been obtained for higher forms of randomness, i.e. randomness relative to strong oracles. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to different machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing Degree when they are defined with respect to different universal machines.
