Istituto di Scienza e Tecnologie dell'Informazione     
Romani F. Asymptotic properties of program size complexity measure. Internal note IEI-B77-02, 1977.
The program size complexity measure of one argument functions is studied with respect to semantical connections with Information theory. A classification of machines based on the instantaneity properties of their domains is given and a program size measure is introduced also for machines, namely the shortest simulation program on a given machine. With this background, equivalence theorems are proved, linking limit average values of program size complexity and the well know concept of Information Theoretical Entropy. The connection are shown valid also for conditional program size complexity.
Subject Computational complexity
Information theory
Noiseless coding
Program size

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional