Order:
Disambiguations
Veronica Becher [11]V. Becher [1]
  1. A Highly Random Number.Veronica Becher & Sergio Daicz - unknown
    many symbols. We define o, as the probability that an arbitrary machine be circular and we prove that o, is a random number that goes beyond..
    No categories
     
    Export citation  
     
    Bookmark   5 citations  
  2.  10
    The descriptive complexity of the set of Poisson generic numbers.Verónica Becher, Stephen Jackson, Dominik Kwietniak & Bill Mance - forthcoming - Journal of Mathematical Logic.
    Let [Formula: see text] be an integer. We show that the set of real numbers that are Poisson generic in base [Formula: see text] is [Formula: see text]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [Formula: see text] and not Poisson generic in base [Formula: see text] is complete for the class given by the differences between [Formula: see text] sets. We also show that the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  3. Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
    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$ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  58
    Randomness and Halting Probabilities.VeróNica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1411 - 1430.
    We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is $\Sigma _{n}^{0}$-complete or $\Pi _{n}^{0}$-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is $\Sigma _{n}^{0}$ or $\Pi _{n}^{0}$ Nevertheless, there exists $\Delta _{n+1}^{0}$ sets such that ΩU[X] is n-random. There are $\Delta _{2}^{0}$ sets (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  5.  92
    Random reals and possibly infinite computations Part I: Randomness in ∅'.Verónica Becher & Serge Grigorieff - 2005 - Journal of Symbolic Logic 70 (3):891-913.
    Using possibly infinite computations on universal monotone Turing machines, we prove Martin-Löf randomness in ∅' of the probability that the output be in some set.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  25
    Index of Authors of Volume 14.N. Alechina, A. Altman, V. Becher, G. A. Bodanza, T. Braüner, A. Branco, P. Buitelaar, J. Cantwell, H. De Nivelle & S. Degeilh - 2005 - Journal of Logic, Language and Information 14 (4):489.
  7.  44
    Turing's normal numbers: towards randomness.Verónica Becher - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 35--45.
  8.  47
    Conference on Computability, Complexity and Randomness.Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson - 2008 - Bulletin of Symbolic Logic 14 (4):548-549.
  9.  38
    From index sets to randomness in ∅ n : random reals and possibly infinite computations. Part II.Verónica Becher & Serge Grigorieff - 2009 - Journal of Symbolic Logic 74 (1):124-156.
    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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  10. Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
    In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  43
    (1 other version)Logic, Computability, and Randomness.Verónica Becher - 2005 - Bulletin of Symbolic Logic 11 (4):557-557.