Can Every Analog System Be Simulated On A Digital Computer?

A Turing machine is a model describing the fundamental limits of any realizable computer, digital signal processor (DSP), or field programmable gate array (FPGA). This paper shows that there exist very simple linear time-invariant (LTI) systems which can not be simulated on a Turing machine. In particular, this paper considers the linear system described by the voltage-current relation of an ideal capacitor. For this system, it is shown that there exist continuously differentiable and computable input signals such that the output signal is a continuous function which is not computable. Moreover, for this particular system, we present sharp results characterizing computable input signals which guarantee that the output signal is computable. Additionally, it is shown that the computability of the step response of an LTI system does not necessarily imply that the impulse response is computable.