8 found
Sort by:
  1. 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  
  2. 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  
  3. Marie Ferbus‐Zanda & Serge Grigorieff (2006). Kolmogorov Complexity and Set Theoretical Representations of Integers. Mathematical Logic Quarterly 52 (4):375-403.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. 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  
  5. Loïc Colson & Serge Grigorieff (2001). Syntactical Truth Predicates for Second Order Arithmetic. Journal of Symbolic Logic 66 (1):225-256.
    We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA 2 . An s.t.p. is a set T of closed formulas such that: (i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation (ii) T(A → B) if and only if (T(A) $\Longrightarrow$ T(B)) (iii) T(∀ x A) if and only if (T(A[x ← t]) for any closed first (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  6. Sanjeev Arora, Matthias Baaz, Lenore Blum, Patrick Dehornoy, Solomon Feferman, Moti Gitik, Erich Grädel, Yuri Gurevich, Serge Grigorieff & David Harel (1995). Clermont-Ferrand, France, July 21–30, 1994. Bulletin of Symbolic Logic 1 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  7. Serge Grigorieff (1990). Every Recursive Linear Ordering has a Copy in Dtime-Space (N, Log(N)). Journal of Symbolic Logic 55 (1):260-276.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  8. Serge Grigorieff (1971). Combinatorics on Ideals and Forcing. Annals of Mathematical Logic 3 (4):363-394.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation