Complexity analysis for algorithmically simple strings

Details Complexity analysis for algorithmically simple strings Complexity analysis for algorithmically simple strings

2000-09-05

arxiv.org/abs/cs/0009001v3

Computer Science

Learning

10 pages

Scientific paper

Given a reference computer, Kolmogorov complexity is a well defined function on all binary strings. In the standard approach, however, only the asymptotic properties of such functions are considered because they do not depend on the reference computer. We argue that this approach can be more useful if it is refined to include an important practical case of simple binary strings. Kolmogorov complexity calculus may be developed for this case if we restrict the class of available reference computers. The interesting problem is to define a class of computers which is restricted in a {\it natural} way modeling the real-life situation where only a limited class of computers is physically available to us. We give an example of what such a natural restriction might look like mathematically, and show that under such restrictions some error terms, even logarithmic in complexity, can disappear from the standard complexity calculus. Keywords: Kolmogorov complexity; Algorithmic information theory.

Affiliated with

Also associated with

No associations

Rating

Complexity analysis for algorithmically simple strings 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 Complexity analysis for algorithmically simple strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity analysis for algorithmically simple strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-433273