Real Recursive Functions and Baire Classes

• Autorzy: Mycka J.
• Języki publikacji: EN

Abstrakty

EN

Recursive functions over the reals [6] have been considered, first as a model of analog computation, and second to obtain analog characterizations of classical computational complexity classes [2]. However, one of the operators introduced in the seminal paper by Cris Moore (in 1996), the minimalization operator, creates some difficulties: (a) although differential recursion (the analog counterpart of classical recurrence) is, to some extent, directly implementable in the General Purpose Analog Computer of Claude Shannon, analog minimalization is far from physical realizability, and (b) analog minimalization was borrowed from classical recursion theory and does not fit well the analytic realm of analog computation. In this paper we use the most natural operator captured from Analysis - the operator of taking a limit - instead of the minimalization with respect to the equivalance of these operators given in [8]. In this context the natural question about coincidence between real recursive functions and Baire classes arises. To solve this problem the limit hierarchy of real recursive funcions is introduced. Relations between Baire classes, effective Baire classes and the limit hierachy are also studied.

Słowa kluczowe

EN

theory of computation; real recursive functions; hierarchy of real functions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 65, nr 3
• Strony: 263--278
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Mycka J.

• Institute of Mathematics M.Curie-Skłodowska University pl. M.Curie-Skłodowskiej 1, 20-031 Lublin, Poland,

Bibliografia

• [1] Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NPcompletness, recursive functions and universal machines, Bull. Amer. Math. Soc., 21, 1989, 1–46.
• [2] Campagnolo,M.: The complexity of real recursive functions, Unconventional Models of Computation, UMC 2002 (C. Calude, M. Dinneen, F. Peper, Eds.), LNCS, Springer-Verlag, 2002, 1–14.
• [3] Campagnolo, M., Moore, C., Costa, J.: Iteration, inequalities, and differentiability in analog computers, Journal of Complexity, 16(4), 2000, 642–660.
• [4] Campagnolo, M., Moore, C., Costa, J.: An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity, 18(4), 2002, 977–1000.
• [5] Grzegorczyk, A.: On the definition of computable real continuous functions, Fund. Math., 44, 1957, 61–71.
• [6] Moore, C.: Recursion theory on the reals and continuous-time computation, Theoretical Computer Science, 162, 1996, 23–44.
• [7] Moschovakis, Y.: Descriptive Set Theory, North-Holland, 1980.
• [8] Mycka, J.: μ-Recursion and infinite limits, Theoretical Computer Science, 302, 2003, 123–133.
• [9] Mycka, J., Costa, J.: Real recursive functions and their hierarchy, Journal of Complexity, in print.
• [10] Rubel, L.: Some mathematical limitations of the General-Purpose Analog Computer, Advances in Applied Mathematics, 9, 1988, 22–34.
• [11] Rubel, L.: The Extended Analog Computer, Advances in Applied Mathematics, 14, 1993, 39–50.
• [12] Shannon, C.: Mathematical theory of the differential analyser, J. Math. Phys. MIT, 20, 1941, 337–354.