INVESTIGADORES
BECHER veronica Andrea
artículos
Título:
Kolmogorov Complexity for Possibly Infinite Computations
Autor/es:
BECHER, VERÓNICA; FIGUEIRA, SANTIAGO
Revista:
Journal of Logic Language and Information
Editorial:
Springer
Referencias:
Año: 2005 vol. 14 p. 133 - 148
ISSN:
0925-8531
Resumen:
We study a variant of the Kolmogorov complexity for possibly infinite computations, that is, either halting or non-halting computations on Turing machines.This complexity function is defined as the length of the shortest inputs that produce a desired output via a possibly non-halting computation. We study several properties of the graph of this complexity function, specially its oscillations with respect to the classical complexity for effective computations.
