Atlas home || Conferences | Abstracts | about Atlas

1998 New Zealand Mathematics Colloquium
July 6-9, 1998
Victoria University of Wellington
Wellington, New Zealand

Organizers
Peter Donelan, Chris Atkin, John Harper, Philip Rhodes-Robinson, Jim Neyland, Geoff Whittle, Steve White, Vladimir Pestov, Tom Crosby

View Abstracts
Conference Homepage

Some variations on program-size complexity and hypersimple sets
by
Asat Arslanov
University of Auckland and Chebotarev Research Institute (Russia)

We study here some computability theoretic properties of two notions of randomness for finite strings: Kolomogorov's randomness based on the blank-endmarker complexity measure and Chaitin's randomness based on the self-delimiting complexity measure. For example, we find the positions of RANDK and RANDC to be 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.

Date received: June 11, 1998

Copyright © 1998 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cabd-47.