Axiomatizing analog algorithms

DOI10.1007/978-3-319-40189-8_22MaRDI QIDQ3188259zbMATH OpenOpenAlexFDO

Authors Nachum Dershowitz, Pierre Neron, Olivier Bournez

Publication date 17 August 2016

Published in Pursuit of the Universal (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) General topics in the theory of algorithms (68W01)

Abstract: We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.

Recommendations

• scientific article; zbMATH DE number 7340320
• The algorithmic analysis of hybrid systems
• Abstract state machines capture parallel algorithms
• Analog computers and recursive functions over the reals.
• scientific article; zbMATH DE number 4076602

Cites work

• A Natural Axiomatization of Computability and Proof of Church's Thesis
• A survey on continuous time computations
• Analog computers and recursive functions over the reals.
• Axiomatizing analog algorithms
• Computational bounds on polynomial differential equations
• Differential dynamic logic for hybrid systems
• Mathematical Theory of the Differential Analyzer
• Models of computation for partial functions on the reals
• New Computational Paradigms
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Gurevich's theorem on sequential algorithms
• Programming with Infinitesimals: A While-Language for Hybrid System Modeling
• Sequential abstract-state machines capture sequential algorithms
• The Church-Turing Thesis over Arbitrary Domains
• The differential analyzer. A new machine for solving differential equations
• Three paths to effectiveness
• Towards an Axiomatization of Simple Analog Algorithms

Cited in

(5)

• Towards an Axiomatization of Simple Analog Algorithms
• A Differentially Algebraic Replacement Theorem, and Analog Computability
• Axiomatizing analog algorithms
• A Survey on Analog Models of Computation
• What is the Church-Turing Thesis?

This page was built for publication: Axiomatizing analog algorithms

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