TY - GEN
T1 - Can every analog system be simulated on a digital computer?
AU - Boche, Holger
AU - Pohl, Volker
N1 - Publisher Copyright:
© 2020 IEEE
PY - 2020/5
Y1 - 2020/5
N2 - 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.
AB - 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.
KW - Computability
KW - Linear time-invariant systems
KW - Stable systems
KW - Turing machines
UR - http://www.scopus.com/inward/record.url?scp=85091158078&partnerID=8YFLogxK
U2 - 10.1109/ICASSP40776.2020.9054494
DO - 10.1109/ICASSP40776.2020.9054494
M3 - Conference contribution
AN - SCOPUS:85091158078
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 1783
EP - 1787
BT - 2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020
Y2 - 4 May 2020 through 8 May 2020
ER -