6 found
Order:
  1. Every recursive linear ordering has a copy in dtime-space (n, log(n)).Serge Grigorieff - 1990 - Journal of Symbolic Logic 55 (1):260-276.
  2.  25
    Kolmogorov complexity and set theoretical representations of integers.Marie Ferbus-Zanda & Serge Grigorieff - 2006 - Mathematical Logic Quarterly 52 (4):375-403.
    We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  60
    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  
  4.  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  
  5.  40
    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  
  6.  48
    Syntactical truth predicates for second order arithmetic.Loïc Colson & Serge Grigorieff - 2001 - 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 (8 more)  
     
    Export citation  
     
    Bookmark