9 found
Sort by:
  1. Veronica Becher & Sergio Daicz, A Highly Random Number.
    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
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  2. Verónica Becher (2012). Turing's Normal Numbers: Towards Randomness. In. In S. Barry Cooper (ed.), How the World Computes. 35--45.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Verónica Becher & Serge Grigorieff (2009). From Index Sets to Randomness in ∅ N : Random Reals and Possibly Infinite Computations. Part II. 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)  
     
    My bibliography  
     
    Export citation  
  4. 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). Conference on Computability, Complexity and Randomness. Bulletin of Symbolic Logic 14 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  5. Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller (2006). Randomness and Halting Probabilities. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Verónica Becher (2005). Logic, Computability, and Randomness. Bulletin of Symbolic Logic 11 (4):557-557.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  7. Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  8. Verónica Becher & Serge Grigorieff (2005). Random Reals and Possibly Infinite Computations Part I: Randomness in ∅'. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Joos Heintz, Antonın Kucera, Joseph Miller, André Nies, Jan Reimann, Theodore Slaman, Diego Vaggione, Paul Vitányi & Verónica Becher (2005). Córdoba, Argentina September 20–24, 2004. Bulletin of Symbolic Logic 11 (4).
    Direct download  
     
    My bibliography  
     
    Export citation