Conference Paper/Proceeding/Abstract 180 views 21 downloads
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
Leibniz International Proceedings in Informatics (LIPIcs), Volume: 345, Pages: 79:1 - 79:20
Swansea University Author:
Eike Neumann
-
PDF | Version of Record
© Eike Neumann. Licensed under a Creative Commons License CC-BY 4.0.
Download (818.85KB)
DOI (Published version): 10.4230/LIPIcs.MFCS.2025.79
Abstract
We study the problem of deciding whether a point escapes a closed subset of ℝ^d under the iteration of a continuous map f : ℝ^d → ℝ^d in the bit-model of real computation. We give a sound partial decision method for this problem which is complete in the sense that its halting set contains the haltin...
| Published in: | Leibniz International Proceedings in Informatics (LIPIcs) |
|---|---|
| ISBN: | 978-3-95977-388-1 |
| ISSN: | 1868-8969 |
| Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2025
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa70345 |
| Abstract: |
We study the problem of deciding whether a point escapes a closed subset of ℝ^d under the iteration of a continuous map f : ℝ^d → ℝ^d in the bit-model of real computation. We give a sound partial decision method for this problem which is complete in the sense that its halting set contains the halting set of all sound partial decision methods for the problem. Equivalently, our decision method terminates on all problem instances whose answer is robust under all sufficiently small perturbations of the function. We further show that the halting set of our algorithm is dense in the set of all problem instances. While our algorithm applies to general continuous functions, we demonstrate that it also yields complete decision methods for much more rigid function families: affine linear systems and quadratic complex polynomials. In the latter case, completeness is subject to the density of hyperbolicity conjecture in complex dynamics. This in particular yields an alternative proof of Hertling’s (2004) conditional answer to a question raised by Penrose (1989) regarding the computability of the Mandelbrot set. |
|---|---|
| Keywords: |
Dynamical Systems, Computability in Analysis, Non-Linear Functions |
| College: |
Faculty of Science and Engineering |
| Funders: |
Swansea University |
| Start Page: |
79:1 |
| End Page: |
79:20 |