Author(s): Costa, José Félix
Date: 2012
Origin: Boletim da Sociedade Portuguesa de Matemática
Subject(s): Artigos
Document details
Turing Machines as Clocks, Rulers and Randomizers
Description
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.
Document Type
Journal article
Language Portuguese
Language Portuguese
