Abstract

The classical model of computability is the theory of partial recursive functions. Church’s thesis postulates the “universality” of this model, and a vast corpus of other approaches confirms this thesis. Partial recursive functions is the minimal subset of partial functions containing a list of elementary functions and stable wrt another list of basic operations. One part of my talk is dedicated to the operad generated by basic operations, and possibly larger algebras over this operad formalizing also oracle assisted computations. Another part will deal with applications of computability and complexity to the creation of a mathematical model of Zipf’s law: empirical probability measure observable on a vast amount of data, starting with distribution of words in texts.