Author(s):
Costa, José Félix; Technical University of Lisbon 
Date: 2014
Origin: Boletim da Sociedade Portuguesa de Matemática
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 thatit can be seen as a contribution to the understanding of computationalcomplexity. The article is educational and first ideas about Turing machines,computation and classes are introduced from scratch. However, the expectedexamples of Turing machine computations are focused in the fundamental,nevertheless “semi-obscure” subject of the alarm clock and space boundruler.
In this paper we specify Turing machines to serve as clocks, rulers,and randomizers of the most basic complexity classes in such a way thatit can be seen as a contribution to the understanding of computationalcomplexity. The article is educational and first ideas about Turing machines,computation and classes are introduced from scratch. However, the expectedexamples of Turing machine computations are focused in the fundamental,nevertheless “semi-obscure” subject of the alarm clock and space boundruler.
Document Type
Article
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||