On Non-Detectability of Non-Computability and the Degree of Non-Computability of Solutions of Circuit and Wave Equations on Digital Computers

DOI10.1109/TIT.2022.3172837MaRDI QIDQ5097008zbMATH OpenOpenAlexFDO

Authors Holger Boche, Volker Pohl

Publication date 19 August 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.12626

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Analytic circuit theory (94C05) Complexity of computation (including implicit computational complexity) (03D15)

Abstract: It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input--output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing.

Recommendations

• scientific article; zbMATH DE number 7385902
• On the (non) NP-hardness of computing circuit complexity
• scientific article; zbMATH DE number 1797000
• On non-classical theory of computability
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• Computability of Solutions of the Korteweg-de Vries Equation
• Computability of analog networks
• Computability and incomputability of differential equations
• On digital nondeterminism
• Computing the solution of the nonlinear Klein-Gordon equation by Turing machines

This page was built for publication: On Non-Detectability of Non-Computability and the Degree of Non-Computability of Solutions of Circuit and Wave Equations on Digital Computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097008)