4 results for Arslanov, A

  • On Hypersimple Sets and Chaitin Complexity

    Arslanov, A (1998-04)

    Report
    The University of Auckland Library

    In this paper we study some computability theoretic properties of two notions of randomness for finite strings: randomness based on the blank-endmarker complexity measure and Chaitin randomness based on the self-delimiting complexity measure. For example, we find the position of RANDK and RANDC at the same level in the scale of immunity notions by proving that both of them are not hyperimmune sets. Also we introduce a new notion of complex infinite sequences of finite strings. We call them K-bounded sequences.

    View record details
  • Difference Splittings of Recursively Enumerable Sets

    Arslanov, A (1996-01)

    Report
    The University of Auckland Library

    We study here the degree-theoretic structure of set-theoretical splittings of recursively enumerable (r.e.) sets into differences of r.e. sets. As a corollary we deduce that the ordering of wtt-degrees of unsolvability of differences of r.e. sets is not a distributive semilattice and is not elementarily equivalent to the ordering of r.e. wtt-degrees of unsolvability.

    View record details
  • Program-Size Complexity Computes the Halting Problem

    Chaitin, G.J; Arslanov, A; Calude, C (1995-09)

    Report
    The University of Auckland Library

    Can the halting problem be solved if one could compute program-size complexity? The answer is yes and here are two different proofs.

    View record details
  • On a Conjecture of M. Van Lambalgen

    Arslanov, A (1997-05)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details