Kolmogorov complexities Kmax, Kmin on computable partially ordered sets
| dc.creator | Ferbus-Zanda, Marie | |
| dc.creator | Grigorieff, Serge | |
| dc.date | 2008-01-02 | |
| dc.date.accessioned | 2026-07-07T08:52:33Z | |
| dc.date.available | 2026-07-07T08:52:33Z | |
| dc.description | We introduce a machine free mathematical framework to get a natural formalization of some general notions of infinite computation in the context of Kolmogorov complexity. Namely, the classes Max^{X\to D}_{PR} and Max^{X\to D}_{Rec} of functions X \to D which are pointwise maximum of partial or total computable sequences of functions where D = (D,<) is some computable partially ordered set. The enumeration theorem and the invariance theorem always hold for Max^{X\to D}_{PR}, leading to a variant KD;max of Kolmogorov complexity. We characterize the orders D such that the enumeration theorem (resp. the invariance theorem) also holds for Max^{X\to D}_{Rec} . It turns out that Max^{X\to D}_{Rec} may satisfy the invariance theorem but not the enumeration theorem. Also, when Max^{X\to D}_{Rec} satisfies the invariance theorem then the Kolmogorov complexities associated to Max^{X\to D}_{Rec} and Max^{X\to D}_{PR} are equal (up to a constant). Letting K^D_{min} = K^{D^{rev}}_{max}, where D^{rev} is the reverse order, we prove that either K^D_{min} =_{ct} K^D_{max} =_{ct} K^D (=_{ct} is equality up to a constant) or K^D_{min}, K^D_{max} are <=_{ct} incomparable and <_{ct} K^D and >_{ct} K^{0',D}. We characterize the orders leading to each case. We also show that K^D_{min}, K^D_{max} cannot be both much smaller than K^D at any point. These results are proved in a more general setting with two orders on D, one extending the other. | |
| dc.description | 35 pages | |
| dc.identifier | https://arxiv.org/abs/0801.0351 | |
| dc.identifier | http://arxiv.org/abs/0801.0351 | |
| dc.identifier | Theoretical Computer Science 352 (2006) 159-180 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/145313 | |
| dc.subject | Logic | |
| dc.subject | Logic in Computer Science | |
| dc.title | Kolmogorov complexities Kmax, Kmin on computable partially ordered sets | |
| dc.type | text |