Mathematics – Logic
Scientific paper
2008-01-02
Mathematical Logic Quaterly 52, Number 4 (2006) 375-403
Mathematics
Logic
56 pages
Scientific paper
10.1002/malq.200510040
We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations), in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of "self-enumerated system" that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations. This contrasts with the well-known fact that usual Kolmogorov complexity does not depend (up to a constant) on the chosen arithmetic representation of integers, let it be in any base unary, binary et so on. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics.
Ferbus-Zanda Marie
Grigorieff Serge
No associations
LandOfFree
Set theoretical Representations of Integers, I 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 Set theoretical Representations of Integers, I, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set theoretical Representations of Integers, I will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-495933