Kolmogorov complexity for possibly infinite computations

In this paper we study a variant of the Kolmogorov complexity for non-effective 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 comp...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Figueira, Santiago, Becher, Verónica
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2003
Materias:
Ciencias Informáticas
Computational logic
Connection machines
Kolmogorov complexity
Program-size complexity
Turing machines
monotone machines
infinite computations
non-effective computations
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/22767
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-22767
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Computational logic
Connection machines
Kolmogorov complexity
Program-size complexity
Turing machines
monotone machines
infinite computations
non-effective computations
spellingShingle Ciencias Informáticas
Computational logic
Connection machines
Kolmogorov complexity
Program-size complexity
Turing machines
monotone machines
infinite computations
non-effective computations
Figueira, Santiago
Becher, Verónica
Kolmogorov complexity for possibly infinite computations
topic_facet Ciencias Informáticas
Computational logic
Connection machines
Kolmogorov complexity
Program-size complexity
Turing machines
monotone machines
infinite computations
non-effective computations
description In this paper we study a variant of the Kolmogorov complexity for non-effective 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. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations.
format Objeto de conferencia
Objeto de conferencia
author Figueira, Santiago
Becher, Verónica
author_facet Figueira, Santiago
Becher, Verónica
author_sort Figueira, Santiago
title Kolmogorov complexity for possibly infinite computations
title_short Kolmogorov complexity for possibly infinite computations
title_full Kolmogorov complexity for possibly infinite computations
title_fullStr Kolmogorov complexity for possibly infinite computations
title_full_unstemmed Kolmogorov complexity for possibly infinite computations
title_sort kolmogorov complexity for possibly infinite computations
publishDate 2003
url http://sedici.unlp.edu.ar/handle/10915/22767
work_keys_str_mv AT figueirasantiago kolmogorovcomplexityforpossiblyinfinitecomputations
AT becherveronica kolmogorovcomplexityforpossiblyinfinitecomputations
bdutipo_str Repositorios
_version_ 1764820467675299841

Ejemplares similares