2016/05/05 by Anatol Slissenko, Slissenko, Anatol
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Neural Networks and Applications #Statistical and Computational Modeling
paper · pdf · doi:10.48550/arxiv.1605.01519
openalex publication_date 2016/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper describes an approach to measuring convergence of an algorithm to its result in terms of an entropy-like function of partitions of its inputs of a given length. The goal is to look at the algorithmic data processing from the viewpoint of information transformation, with a hope to better understand the work of algorithm, and maybe its complexity. The entropy is a measure of uncertainty, it does not correspond to our intuitive understanding of information. However, it is what we have in this area. In order to realize this approach we introduce a measure on the inputs of a given length based on the Principle of Maximal Uncertainty: all results should be equiprobable to the algorithm at the beginning. An algorithm is viewed as a set of events, each event is an application of a command. The commands are very basic. To measure the convergence we introduce a measure that is called entropic weight of events of the algorithm. The approach is illustrated by two examples.