RUS  ENG
Full version
JOURNALS // Preprints of the Keldysh Institute of Applied Mathematics // Archive

Keldysh Institute preprints, 2001 019 (Mi ipmp1071)

Continuous fractions, complexity of rational nubmbers and languages with infinite alphabet

A. V. Vorozhtsov


Abstract: In this paper continuous fractions are treated as description language of rational numbers. Alphabet of the language is natural numbers $N$ — infinite set. So standard definition of complexity (a la A. N. Kolmogorov) is not applicable. New approach is needed. Here you find one natural way to define complexity in the case of infinite countable languages. Besides, some known results about continuous fractions and some news, drawing from this new approach are stated. There are new tasks related with the complexity distributions and efficiency of a description language.



© Steklov Math. Inst. of RAS, 2024