Mathematics – Logic
Scientific paper
2008-01-02
Theoretical Computer Science 352 (2006) 159-180
Mathematics
Logic
35 pages
Scientific paper
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.
Ferbus-Zanda Marie
Grigorieff Serge
No associations
LandOfFree
Kolmogorov complexities Kmax, Kmin on computable partially ordered sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Kolmogorov complexities Kmax, Kmin on computable partially ordered sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexities Kmax, Kmin on computable partially ordered sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-495926