Abstract

Invariance of the class of algorithms expressible with respect to changes in computational formalism have provided extremely stable foundations for the Church-Turing thesis, according to which a number of—equivalent—computational mechanisms each fully capture the intuitive notion of algorithm. Thanks to the stability and elegance of the Church-Turing thesis, the notion of computation defined by these mechanisms is etched in stone as the theoretical essence of computation. In particular, this notion has been extensively used as an abstract tool to model natural phenomena.