nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Tracking Computability of GPAC-Generable Functions

verfasst von : Diogo Poças, Jeffery Zucker

Erschienen in: Logical Foundations of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. A pioneering model is the General Purpose Analog Computer (GPAC), initially presented by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams; however, it has been shown to be strictly less powerful than other models of computation on the reals, such as computable analysis.

In previous work, we proposed an extension of the Shannon GPAC, denoted LGPAC, designed to overcome its limitations. Not only is the LGPAC model capable of expressing computation over general data spaces \(\mathcal {X}\), it also directly incorporates approximating computations by means of a limit module. In this paper, we compare the LGPAC with a digital model of computation based on effective representations (tracking computability). We establish general conditions under which LGPAC-generable functions are tracking computable.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Parameterised Complexity of Abduction in Schaefer’s Framework

Nächstes Kapitel Modal Type Theory Based on the Intuitionistic Modal Logic

Nur mit Berechtigung zugänglich

More details can be found in [11, 12].

Here, assumption (1d), that the original family of pseudonorms on \(\mathcal {X}\) is nondecreasing, is required; alternatively, one could introduce a double-indexing family such as \(\Vert u\Vert _{n,m}=\Vert u(0)\Vert _n+\sup _{0\le t\le m}\Vert u'(t)\Vert _n\).

By assumption, addition and scalar multiplication are defined on \(\mathcal {X}\). The integral can be generalized to \(C^1(\mathbb {T},\mathcal {X})\) via Riemann sums: see, for example, [14, p. 89].

For ease of notation we write \(\alpha \{T\}(n)\) instead of \(\alpha (\{T\}(n))\).

The computability of basic algebraic operations is usually one of the first results to be proved for a model of computation. For example, in the framework of computable analysis, this is proved in [10, Sect. 0.4]; and in the framework of type-2 theory of effectivity, this is proved in [22, Sect. 2.1]. The techniques carry over to the tracking computability framework in this paper.

Observe that \(t_j\le 2^{t_j-1}\) for any \(t_j=j+2\ge 2\).

Bournez, O., Campagnolo, M.L., Graça, D.S., Hainry, E.: Polynomial differential equations compute all real computable functions on computable compact intervals. J. Complex. 23(3), 317–335 (2007). https://doi.org/10.1016/j.jco.2006.12.005MathSciNetCrossRefMATH

Bush, V.: The differential analyzer. A new machine for solving differential equations. J. Frankl. Inst. 212(4), 447–488 (1931)CrossRef

Campagnolo, M.L., Moore, C., Costa, J.F.: Iteration, inequalities, and differentiability in analog computers. J. Complex. 16(4), 642–660 (2000). https://doi.org/10.1006/jcom.2000.0559MathSciNetCrossRefMATH

Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. Tata McGraw-Hill Education, New York (1955)MATH

Graça, D.S., Campagnolo, M.L., Buescu, J.: Robust simulations of turing machines with analytic maps and flows. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 169–179. Springer, Heidelberg (2005). https://doi.org/10.1007/11494645_21CrossRef

Hartree, D.R.: Calculating Instruments and Machines. Cambridge University Press, Cambridge (1950) MATH

Kohlenbach, U., Lambov, B.: Bounds on iterations of asymptotically quasi-nonexpansive mappings. BRICS Rep. Ser. 10(51) (2003)

Kohlenbach, U., Leuştean, L.: Asymptotically nonexpansive mappings in uniformly convex hyperbolic spaces. J. Eur. Math. Soc. 12(1), 71–92 (2010). https://doi.org/10.4171/JEMS/190MathSciNetCrossRefMATH

Mal’cev, A.I.: Constructive algebras I. Rus. Math. Surv. 16, 77–129 (1961)MathSciNetCrossRef

10.

Pour-El, M.B., Richards, I.: Computability in Analysis and Physics. Springer, Heidelberg (1989)CrossRef

11.

Poças, D., Zucker, J.: Analog networks on function data streams. Computability 7(4), 301–322 (2018). https://doi.org/10.3233/COM-170077MathSciNetCrossRefMATH

12.

Poças, D., Zucker, J.: Approximability in the GPAC. Log. Methods Comput. Sci. 15(3) (2019). https://doi.org/10.23638/LMCS-15(3:24)2019

13.

Reed, M., Simon, B.: Methods of Modern Mathematical Physics: Functional Analysis. Academic Press Inc., Cambridge (1980)MATH

14.

Rudin, W.: Principles of Mathematical Analysis. International Series in Pure and Applied Mathematics, 3rd edn. McGraw-Hill, New York (1976)MATH

15.

Shannon, C.: Mathematical theory of the differential analyser. J. Math. Phys. 20, 337–354 (1941)CrossRef

16.

Stoltenberg-Hansen, V., Tucker, J.V.: Effective algebras. Handbook of Logic in Computer Science, vol. 4, pp. 357–526. Oxford University Press, Oxford (1995)

17.

Stoltenberg-Hansen, V., Tucker, J.V.: Concrete models of computation for topological algebras. Theoret. Comput. Sci. 219(1–2), 347–378 (1999)MathSciNetCrossRef

18.

Thomson, W., Tait, P.: Treatise on Natural Philosophy, 2nd edn, pp. 479–508. Cambridge University Press, Cambridge (1880)MATH

19.

Tucker, J.V., Zucker, J.I.: Abstract versus concrete computation on metric partial algebras. ACM Trans. Comput. Logic (TOCL) 5(4), 611–668 (2004). https://doi.org/10.1145/1024922.1024924MathSciNetCrossRefMATH

20.

Tucker, J.V., Zucker, J.I.: Computable total functions on metric algebras, universal algebraic specifications and dynamical systems. J. Logic Algebraic Program. 62(1), 71–108 (2005). https://doi.org/10.1016/j.jlap.2003.10.001 MathSciNetCrossRefMATH

21.

Tucker, J.V., Zucker, J.I.: Abstract versus concrete computability: the case of countable algebras. In: Stoltenberg-Hansen, V., Väänänen, J. (eds.) Logic Colloquium ’03. Lecture Notes in Logic, pp. 377–408. Cambridge University Press, Cambridge (2006). https://doi.org/10.1017/9781316755785.019

22.

Weihrauch, K.: Computable Analysis: An Introduction. Texts in Theoretical Computer Science. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-642-56999-9CrossRefMATH

Titel: Tracking Computability of GPAC-Generable Functions
verfasst von: Diogo Poças
Jeffery Zucker
Verlag: Springer International Publishing
Buch: Logical Foundations of Computer Science
Print ISBN: 978-3-030-36754-1

Electronic ISBN: 978-3-030-36755-8

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-36755-8_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"