Computable Analysis as a Framework for Computability over Continuous Domains

This presentation explores computable analysis as a framework for reasoning about computability over continuous domains, with applications to cyber-physical and hybrid systems. It begins with an introduction to classical notions of computability, the Church–Turing thesis, and complexity theory, before highlighting the challenges posed by continuous data in engineering systems. Through case studies such as the Patriot missile failure and Ariane 5 explosion, the talk emphasizes the risks of discretization errors in safety-critical contexts. Computable analysis is then introduced as a rigorous mathematical approach to bridge computability theory with real analysis, enabling formal representation and study of continuous processes. The presentation examines reachability problems in dynamical systems, including piecewise constant derivative systems and piecewise affine systems, and discusses key decidability and complexity results (NP-completeness, co-NP, PSPACE). By linking theory with practical modeling challenges, the talk demonstrates how computable analysis provides foundational tools for verifying and reasoning about hybrid and cyber-physical systems.