Abstract: Brief consideration is given to some properties of three measures of complexity based on the length of minimal descriptive programs. Although the measures explicitly deal with finite sequences, the complexity of an infinite sequence can be regarded as a function mapping each positive integer n to the complexity of the initial segment of length n. Some properties of a complexity hierarchy of infinite sequences with respect to one of the measures is considered.
Publication Year: 1969
Publication Date: 1969-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 27
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot