–
Room P3.10, Mathematics Building
Daniel Graça, U Algarve
Turing universality for the GPAC model
The GPAC model was one of the pioneer models for analog computation and was intended to be an abstract model for a computing device, the Differential Analyzer. In this seminar we further exploit this model. In particular we show that, provided we enrich the original model with a unit capable of generating a non-analytic function satisfying some simple conditions, then for each Turing machine we can find a GPAC that simulates any computation of this particular Turing machine. We will show in detail how this argument works and we will also discuss the possibility of introducing complexity measures for the GPAC that can be related with standard complexity measures.