No Cover Image

Conference Paper/Proceeding/Abstract 180 views 21 downloads

Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

Eike Neumann Orcid Logo

Leibniz International Proceedings in Informatics (LIPIcs), Volume: 345, Pages: 79:1 - 79:20

Swansea University Author: Eike Neumann Orcid Logo

  • 70345.VoR.pdf

    PDF | Version of Record

    © Eike Neumann. Licensed under a Creative Commons License CC-BY 4.0.

    Download (818.85KB)

Check full text

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...

Full description

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
first_indexed 2025-09-12T11:55:13Z
last_indexed 2025-10-25T06:47:12Z
id cronfa70345
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2025-10-24T10:16:49.2116369</datestamp><bib-version>v2</bib-version><id>70345</id><entry>2025-09-12</entry><title>Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><ORCID>0009-0003-2907-1566</ORCID><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2025-09-12</date><deptcode>MACS</deptcode><abstract>We study the problem of deciding whether a point escapes a closed subset of &#x211D;^d under the iteration of a continuous map f : &#x211D;^d &#x2192; &#x211D;^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&#x2019;s (2004) conditional answer to a question raised by Penrose (1989) regarding the computability of the Mandelbrot set.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Leibniz International Proceedings in Informatics (LIPIcs)</journal><volume>345</volume><journalNumber/><paginationStart>79:1</paginationStart><paginationEnd>79:20</paginationEnd><publisher>Schloss Dagstuhl &#x2013; Leibniz-Zentrum f&#xFC;r Informatik</publisher><placeOfPublication/><isbnPrint>978-3-95977-388-1</isbnPrint><isbnElectronic/><issnPrint>1868-8969</issnPrint><issnElectronic/><keywords>Dynamical Systems, Computability in Analysis, Non-Linear Functions</keywords><publishedDay>20</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2025</publishedYear><publishedDate>2025-08-20</publishedDate><doi>10.4230/LIPIcs.MFCS.2025.79</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Other</apcterm><funders>Swansea University</funders><projectreference/><lastEdited>2025-10-24T10:16:49.2116369</lastEdited><Created>2025-09-12T12:51:35.6953562</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Eike</firstname><surname>Neumann</surname><orcid>0009-0003-2907-1566</orcid><order>1</order></author></authors><documents><document><filename>70345__35467__184594a8625543c3905bbe53ec0c11f3.pdf</filename><originalFilename>70345.VoR.pdf</originalFilename><uploaded>2025-10-24T10:12:16.7841324</uploaded><type>Output</type><contentLength>838506</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; Eike Neumann. Licensed under a Creative Commons License CC-BY 4.0.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2025-10-24T10:16:49.2116369 v2 70345 2025-09-12 Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space 1bf535eaa8d6fcdfbd464a511c1c0c78 0009-0003-2907-1566 Eike Neumann Eike Neumann true false 2025-09-12 MACS 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. Conference Paper/Proceeding/Abstract Leibniz International Proceedings in Informatics (LIPIcs) 345 79:1 79:20 Schloss Dagstuhl – Leibniz-Zentrum für Informatik 978-3-95977-388-1 1868-8969 Dynamical Systems, Computability in Analysis, Non-Linear Functions 20 8 2025 2025-08-20 10.4230/LIPIcs.MFCS.2025.79 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Other Swansea University 2025-10-24T10:16:49.2116369 2025-09-12T12:51:35.6953562 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 0009-0003-2907-1566 1 70345__35467__184594a8625543c3905bbe53ec0c11f3.pdf 70345.VoR.pdf 2025-10-24T10:12:16.7841324 Output 838506 application/pdf Version of Record true © Eike Neumann. Licensed under a Creative Commons License CC-BY 4.0. true eng https://creativecommons.org/licenses/by/4.0/
title Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
spellingShingle Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
Eike Neumann
title_short Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
title_full Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
title_fullStr Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
title_full_unstemmed Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
title_sort Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Eike Neumann
format Conference Paper/Proceeding/Abstract
container_title Leibniz International Proceedings in Informatics (LIPIcs)
container_volume 345
container_start_page 79:1
publishDate 2025
institution Swansea University
isbn 978-3-95977-388-1
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.MFCS.2025.79
publisher Schloss Dagstuhl – Leibniz-Zentrum für Informatik
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description 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.
published_date 2025-08-20T06:49:23Z
_version_ 1851284168581840896
score 11.090299

Similar Items