10 found
Order:
  1.  91
    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 (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  2.  22
    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 (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  3.  43
    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 (5 more)  
     
    Export citation  
     
    My bibliography  
  4.  12
    Turing's Normal Numbers: Towards Randomness.Verónica Becher - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 35--45.
  5.  8
    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 (6 more)  
     
    Export citation  
     
    My bibliography  
  6.  5
    Logic, Computability, and Randomness.Verónica Becher - 2005 - Bulletin of Symbolic Logic 11 (4):557-557.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  7.  9
    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 (4 more)  
     
    Export citation  
     
    My bibliography  
  8.  3
    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. 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
    Translate
     
     
    Export citation  
     
    My bibliography  
  10.  1
    Córdoba, Argentina September 20–24, 2004.Joos Heintz, Antonın Kucera, Joseph Miller, André Nies, Jan Reimann, Theodore Slaman, Diego Vaggione, Paul Vitányi & Verónica Becher - 2005 - Bulletin of Symbolic Logic 11 (4).
    Direct download  
     
    Export citation  
     
    My bibliography