
We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a continuous value, called continuous time. We relate the two notions of time for general PCD systems. We prove that general PCD systems are equivalent to Turing machines and linear machines in finite discrete time. We prove that the languages recognized by purely rational PCD systems in dimension $d$ in finite continuous time are precisely the languages of the $d-2^{th}$ level of the arithmetical hierarchy. Hence the reachability problem of purely rational PCD systems of dimension $d$ in finite continuous time is $\Sigma_{d-2}$-complete.
computability, modèle de calcul sur les réels, PCD systems, Models of computation (Turing machines, etc.), dynamical system, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], système dynamique, calculabilité, turing machines, Complexity classes (hierarchies, relations among complexity classes, etc.), real computational model
computability, modèle de calcul sur les réels, PCD systems, Models of computation (Turing machines, etc.), dynamical system, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], système dynamique, calculabilité, turing machines, Complexity classes (hierarchies, relations among complexity classes, etc.), real computational model
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
