PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Romani F. Asymptotic properties of program size complexity measure. Internal note IEI-B77-02, 1977.
 
 
Abstract
(English)
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
Entropy
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