Autor(es)

Verónica Becher and Santiago Figueira and André Nies and Silvana Picchi

URL Pública

Abstract

We define a program size complexity function 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 relative to the complexity. We prove that the classes of Martin-Löf random sequences and -random sequences coincide and that the -trivial sequences are exactly the recursive ones. We also study some properties of and compare it with other complexity functions. In particular, is different from , the prefix-free complexity of monotone machines with oracle A.