THE CHURCH THESIS, ITS PROOF, AND THE NOTION OF STABILITY AND STABILIZATION FOR ANALOG ALGORITHMS

TitleTHE CHURCH THESIS, ITS PROOF, AND THE NOTION OF STABILITY AND STABILIZATION FOR ANALOG ALGORITHMS
Publication TypeJournal Article
Year of Publication2019
AuthorsKÖNIGSBERG, ZVIRETCHKIMAN, DERSHOWITZ, NACHUM
Volume23
Issue2
Start Page233
Pagination16
Date Published12/2018
ISSN1083-2564
AMS03B05, 03D99, 68Q01, 93D05
Abstract

This work presents the Church thesis, its proof, and the notion of stability and stabilization for analog algorithms. The Church thesis for discrete algorithms motivates us to consider the Church thesis for the case when we are dealing with analog algorithms. Its presentation and proof follows a similar construction to the one given for discrete algorithms. The notions of analog algorithm and dynamical system are postulated to be equivalent. The stability and stabilization concepts for analog algorithms are defined. The stability and stabilization presentation starts concentrating in continuous and discrete dynamical systems i.e., analog algorithms, described by differential or difference equations and continues considering Lyapunov energy functions.
URLhttps://acadsol.eu/en/articles/23/2/1.pdf
DOI10.12732/caa.v23i2.1
Refereed DesignationRefereed
Full Text

[1] Y. Gurevich, Sequential abstract-state machines capture sequential algorithms, ACM Trans. Comput. Log., 1 (2000).
[2] N. Dershowitz, Y. Gurevich, A natural axiomatization of computability and proof of Church’s Thesis, The Bulletin of Symbolic Logic, 14 (2008).
[3] O. Bournez, N. Dershowitz, Axiomatizing analog algorithms, ArXiv eprints 1604.04295, http://arxiv.org/abs/1604.04295 (2016).
[4] T.Murata, Petri nets: Properties, analysis, and applications, Proc. IEEE, 77 (1989).
[5] Z. Retchkiman, Stability theory for a class of dynamical systems modeled with Petri nets, International Journal of Hybrid Systems, 4, No. 1 (2005).
[6] Z. Retchkiman, Timed Petri net modeling and Lyapunov/Max-Plus-Algebra stability analysis for a type of queuing systems, International Journal of Pure and Applied Mathematics, 86, No. 2 (2013).
[7] J.H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
[8] A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42, Parts 3 and 4 (1936).
[9] A.N. Michel, B. Hu, Towards a stability theory of general hybrid dynamical systems, Automatica, 35 (1999).
[10] V. Lakshmikantham, V.M. Matrosov, S. Sivasundaram, Vector Lyapunov Functions and Stability Analysis of Nonlinear Systems, Kluwer Academic Publ., Dordrecht, 1991.