Encontrados 3 documentos, a visualizar página 1 de 1
Turing Machines as Clocks, Rulers and Randomizers
Costa, José Félix; Technical University of LisbonIn 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 euclid abstract machine
Mycka, Jerzy; Costa, José Félix; Coelho, FranciscoConcrete non-computable functions are usually related to the halting function. Is it possible to present examples of non-computability, which are unrelated to the halting problem and its derivatives? We built an abstract machine based on the historic concept of compass and ruler constructions (a compass construction would suffice) which reveals the existence of non-computable functions not related with the halt...
Analog computers and recursive functions over the reals
Graça, Daniel; Costa, José FelixThis paper revisits one of the rst models of analog computation, the General Purpose Analog Computer (GPAC). In particular, we restrict our attention to the improved model presented in [11] and we show that it can be further re ned. With this we prove the following: (i) the previous model can be simpli ed; (ii) it admits extensions having close connec- tions with the class of smooth continuous time dynamical s...
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||