Affordable Access

Publisher Website

Descriptive complexity of computable sequences

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
271
Identifiers
DOI: 10.1016/s0304-3975(01)00030-5

Abstract

Abstract Our goal is to study the complexity of infinite binary recursive sequences. We introduce several measures of the quantity of information they contain. Some measures are based on size of programs that generate the sequence, the others are based on the Kolmogorov complexity of its finite prefixes. The relations between these complexity measures are established. The most surprising among them are obtained using a specific two-players game 2 2 This paper is the extended version of [4]. .

There are no comments yet on this publication. Be the first to share your thoughts.