Program size complexity for possibly infinite computations

VERÓNICA BECHER; SANTIAGO FIGUEIRA; ANDRÉ NIES; SILVANA PICCHI

NOTRE DAME JOURNAL OF FORMAL LOGIC

University of Notre Dame

Año: 2005 vol. 46 p. 51 - 64

0029-4527

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