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

Ejemplares similares

Ejemplares similares