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

Keldysh Institute preprints, 2005 136, 32 pp. (Mi ipmp777)

About difficulties of the calculations of the arithmetical proGrams

S. V. Popov


Abstract: There are considered program on full base, computing binary all determined functions. It is proved; if function, computed by the program, possess entropy $H$, there is calculation of the program of the length $2_{dH}$ for positive constant $d$.



© Steklov Math. Inst. of RAS, 2024