Program size complexity for possibly infinite computations
We define a program size complexity function H∞ 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}ω relative to the H∞ complexity. We prove th...
Guardado en:
| Autores principales: | Becher, V., Figueira, S., Nies, A., Picchi, S. |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00294527_v46_n1_p51_Becher |
| Aporte de: |
Ejemplares similares
-
Program size complexity for possibly infinite computations
Publicado: (2005) -
Kolmogorov complexity for possibly infinite computations
por: Figueira, Santiago, et al.
Publicado: (2003) -
Another example of higher order randomness
por: Becher, V., et al. -
Another example of higher order randomness
Publicado: (2002) -
Lowness properties and approximations of the jump
por: Figueira, S., et al.
Publicado: (2006)