Autor(es):
Costa, José Félix; Technical University of Lisbon 
Data: 2014
Origem: Boletim da Sociedade Portuguesa de Matemática
Detalhes do Documento
Turing Machines as Clocks, Rulers and Randomizers
Descrição
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.
Tipo de Documento
Artigo
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||