ICTP/SISSA Joint Colloquium in Mathematics - Complexity of Finite Sequences - (as part of the Series of Lectures "Experimental Discoveries of Mathematical Facts")
(Steklov Mathematical Institute, Moscow, Russia)
Everyone understands that the sequence 001001001001 (of 12
binary numbers) is less complicated than the sequence 010010111001. The talk provides an exact mathematical meaning to this complexity notion in terms of the graphs of mappings of finite sets to themselves, leading to a hierarchy of the elements of a finite ring of functions and of its subring of polynomials. Experiments suggest that the most complicated function is the logarithm. The ring of polynomials forms a binary tree with 2^2^k vertices (=2,4,256, ...).
|Maintained by: The CDS Support Team (Bugs and reports)|