Turing Machines as Clocks, Rulers and Randomizers

Resumo

In this paper we specify Turing machines to serve as clocks, rulers,
and randomizers of the most basic complexity classes in such a way that
it can be seen as a contribution to the understanding of computational
complexity. The article is educational and first ideas about Turing machines,
computation and classes are introduced from scratch. However, the expected
examples of Turing machine computations are focused in the fundamental,
nevertheless “semi-obscure” subject of the alarm clock and space bound
ruler.