## Abstract

Solving continuous problems on digital computers gives generally only approximations of the continuous solutions. It is therefore crucial that the error between the continuous solution and the digital approximation can effectively be controlled. This paper investigates the possibility of simulating linear, time-invariant (LTI) systems on Turing machines. It is shown that there exist elementary LTI systems for which an admissible and computable input signal results in a non-computable output signal. For these LTI systems, the paper gives sharp characterizations of input spaces such that the output is guaranteed to be computable. The second part of the paper discusses the computability of the impulse and step response of LTI systems. It is shown that the computability of the step response implies not the computability of the impulse response. Moreover, there exist impulse responses which cannot be computed from the transfer function using the inverse Laplace transform. Finally, the paper gives a stronger version of a classical non-computability result, showing that there exist admissible and computable initial values for the wave equation so that the solution cannot be computed at certain points in space and time.

Original language | English |
---|---|

Article number | 9180285 |

Pages (from-to) | 5051-5064 |

Number of pages | 14 |

Journal | IEEE Transactions on Circuits and Systems I: Regular Papers |

Volume | 67 |

Issue number | 12 |

DOIs | |

State | Published - Dec 2020 |

## Keywords

- Linear time-invariant systems
- computability
- laplace transform
- stable systems
- turing machines