The intrinsic difficulty of recursive functions (Q1919986): Difference between revisions

The paper attempts to offer a robust definition of the notion of an intrinsic (i.e., independent of the computational model) natural complexity measure. The main concept is obtained by using abstract (Blum) complexity measures and smear monoids, a type of monoid introduced here that allows some slack in the comparison of the complexity of recursive functions. Various mathematical and philosophical arguments stress the merits of the concepts introduced in the paper.