Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity

Details Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity

2008-01-02

arxiv.org/abs/0801.0349v1

Dans Denis Richard's 60th Biirthday Conference - Denis Richard's 60th Biirthday Conference, France (2002)

Mathematics

Logic

16 pages

Scientific paper

We consider classical representations of integers: Church's function iterators, cardinal equivalence classes of sets, ordinal equivalence classes of totally ordered sets. Since programs do not work on abstract entities and require formal representations of objects, we effectivize these abstract notions in order to allow them to be computed by programs. To any such effectivized representation is then associated a notion of Kolmogorov complexity. We prove that these Kolmogorov complexities form a strict hierarchy which coincides with that obtained by relativization to jump oracles and/or allowance of infinite computations.

Affiliated with

Also associated with

No associations

Rating

Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity 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 Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495921