Computation with perturbed dynamical systems

Bournez, Olivier; Graca, Daniel S.; Hainry, Emmanuel

http://hdl.handle.net/10400.1/11164

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
handle11164.pdf		270.39 KB	Adobe PDF	Download

Send Feedback

Authors

Bournez, Olivier

Graca, Daniel S.

Hainry, Emmanuel

Abstract(s)

This paper analyzes the computational power of dynamical systems robust to infinitesimal perturbations. Previous work on the subject has delved on very specific types of systems. Here we obtain results for broader classes of dynamical systems (including those systems defined by Lipschitz/analytic functions). In particular we show that systems robust to infinitesimal perturbations only recognize recursive languages. We also show the converse direction: every recursive language can be robustly recognized by a computable system. By other words we show that robustness is equivalent to decidability. (C) 2013 Elsevier Inc. All rights reserved.