A survey of recursive analysis and Moore’s notion of real computation. (English) Zbl 1251.68110
Summary: The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced by Turing, Grzegorczyk and Lacombe. Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996, Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 03B70 | Logic in computer science |
| 03D78 | Computation over the reals, computable analysis |
References:
| [1] | Bellantoni S, Cook S (1992) A new recursion-theoretic characterization of the polytime functions. Comput Complex 2:97–110 · Zbl 0766.68037 |
| [2] | Blondel V, Tsitsiklis J (2000) A survey of computational complexity results in systems and control. Automatica 36(9):1249–1274 · Zbl 0989.93006 |
| [3] | Bournez O, Campagnolo M (2008) A survey on continuous time computations. In: Cooper SB, Löwe B, Sorbi A (eds) New computational paradigms. Changing conceptions of what is computable. Springer-Verlag, New York, pp 383–423 · Zbl 1148.68370 |
| [4] | Bournez O, Hainry E (2004a) An analog characterization of elementarily computable functions over the real numbers. Lecture Notes in Computer Science, vol 3142, pp 269–280 · Zbl 1098.03047 |
| [5] | Bournez O, Hainry E (2004b) Real recursive functions and real extensions of recursive functions. Lecture Notes in Computer Science, vol 3354, pp 116–127 · Zbl 1102.03057 |
| [6] | Bournez O, Hainry E (2005) Elementarily computable functions over the real numbers and $${\(\backslash\)mathbb{R}}$$ -sub-recursive functions. Theor Comput Sci 348(2–3):130–147 · Zbl 1087.03025 |
| [7] | Bournez O, Hainry E (2006) Recursive analysis characterized as a class of real recursive functions. Fundam Inf 74(4):409–433 · Zbl 1152.03049 |
| [8] | Bournez O, Campagnolo M, Graça D, Hainry E (2007) Polynomial differential equations compute all real computable functions on computable compact intervals. J Complex 23(3):317–335 · Zbl 1125.68059 |
| [9] | Bournez O, Gomaa W, Hainry E. Algebraic characterizations of complexity-theoretic classes of real functions. Int J Unconv Comput (accepted) |
| [10] | Bush V (1931) The differential analyzer. A new machine for solving differential equations. J. Franklin Inst. 212:447–488 · Zbl 0003.06504 |
| [11] | Campagnolo M (2001) Computational complexity of real valued recursive functions and analog circuits. PhD thesis, Instituto Superior Técnico |
| [12] | Campagnolo M (2002) The complexity of real recursive functions. Lecture Notes in Computer Science, vol 2509, pp 1–14 · Zbl 1029.03034 |
| [13] | Campagnolo M, Ojakian K (2008) Characterizing computable analysis with differential equations. Electr Notes Theor Comput Sci 221:23–35 · Zbl 1262.03078 |
| [14] | Campagnolo M, Ojakian K (2008) The elementary computable functions over the real numbers: applying two new techniques. Arch Math Log 46(7–8):593–627 · Zbl 1141.03016 |
| [15] | Campagnolo M, Moore C, Costa J (2000a) An analog characterization of the subrecursive functions. In: 4th Conference on real numbers and computers, pp 91–109 |
| [16] | Campagnolo M, Moore C, Costa J (2000b) Iteration, inequalities, and differentiability in analog computers. J Complex16(4):642–660 · Zbl 0967.68075 |
| [17] | Campagnolo M, Moore C, Costa J (2002) An analog characterization of the Grzegorczyk hierarchy. J Complex 18(4):977–1000 · Zbl 1030.68047 |
| [18] | Clote P (1999) Computational models and function algebras. In: Handbook of computability theory. Elsevier, Amsterdam, pp 589–681 · Zbl 0942.68049 |
| [19] | Costa J, Loff B, Mycka J (2009) A foundation for real recursive function theory. Ann Pure Appl Log 160:255–288 · Zbl 1189.03047 |
| [20] | Gakwaya J (1997) A survey of the Grzegorczyk hierarchy and its extension through the BSS model of computability. NeuroCOLT technical report series, technical report, Royal Holloway, University of London. |
| [21] | Gomaa W (2010) Polynomial time computation in the context of recursive analysis. Lecture Notes in Computer Science, vol 6324, pp 146–162 · Zbl 1306.03020 |
| [22] | Gomaa W Rational vs. real computation. Int J Softw Inf (to appear) |
| [23] | Graça DS (2004) Some recent developments on Shannon’s general purpose analog computer. Math Log Quart 50:473–485 · Zbl 1089.68039 |
| [24] | Graça DS, Costa JF (2003) Analog computers and recursive functions over the reals. J Complex 19(5):644–664 · Zbl 1059.68041 |
| [25] | Graça D, Campagnolo M, Buescu J (2005) Robust simulations of Turing machines with analytic maps and flows. Lecture Notes in Computer Science, vol 3526, pp 169–179 · Zbl 1115.68083 |
| [26] | Grzegorczyk A (1953) Some classes of recursive functions. Rosprawy Mat 4:1–45 · Zbl 0052.24902 |
| [27] | Grzegorczyk A (1955) Computable functionals. Fundam Math 42:168–202 · Zbl 0066.26001 |
| [28] | Kalmár L (1943) EgyzzerüPélda Eldönthetetlen Aritmetikai Problémára. Mateés Fizikai Lapok 50:1–23 |
| [29] | Kawamura A (2009) Differential recursion. ACM Trans Comput Log 10(3):1–20 · Zbl 1351.03034 |
| [30] | Ko K-I (1991) Complexity theory of real functions. Birkhäuser, Basel · Zbl 0791.03019 |
| [31] | Lacombe D (1955) Extension de la Notion de Fonction Récursive aux Fonctions d’une ou Plusieurs Variables Réelles III. Compt Rend l’Acad Sci Paris 241:151–153 · Zbl 0066.26101 |
| [32] | Lipshitz L, Rubel LA (1987) A differentially algebraic replacement theorem, and analog computability. Proc Am Math Soc 99(2):367–372 · Zbl 0626.34012 |
| [33] | Loff B, Costa J, Mycka J (2007) Computability on reals, infinite limits and differential equations. Appl Math Comput 191(2):353–371 · Zbl 1193.03083 |
| [34] | Meer K, Michaux C (1997) A survey on real structural complexity theory. Bull Belg Math Soc 4(1):113–148 · Zbl 0934.68046 |
| [35] | Moore C (1996) Recursion theory on the reals and continuous-time computation. Theor Comput Sci 162(1):23–44 · Zbl 0871.68027 |
| [36] | Mycka J (2003) {\(\mu\)}-Recursion and infinite limits. Theor Comput Sci 302:123–133 · Zbl 1044.68056 |
| [37] | Mycka J, Costa J (2004) Real recursive functions and their hierarchy. J Complex 20(6):835–857 · Zbl 1085.03030 |
| [38] | Mycka J, Costa JF (2005) What lies beyond the mountains? Computational systems beyond the turing limit. Eur Assoc Theoret Comput Sci Bull 85:181–189 |
| [39] | Mycka J, Costa J (2006a) The conjecture $$P\(\backslash\)not=NP$$ Presented by means of some classes of real functions. Lecture Notes in Computer Science, vol 3988, pp 47–57 |
| [40] | Mycka J, Costa J (2006b) The $$P\(\backslash\)not=NP$$ conjecture in the context of real and complex analysis. J Complex 22(2):287–303 · Zbl 1156.68387 |
| [41] | Mycka J, Costa J (2007) A new conceptual framework for analog computation. Theor Comput Sci 374:277–290 · Zbl 1164.68005 |
| [42] | Orponen P (1997) A survey of continous-time computation theory. In: Advances in algorithms, languages, and complexity. Springer, Berlin, pp 209–224 · Zbl 0867.68047 |
| [43] | Pour-El MB (1974) Abstract computability and its relation to the general purpose analog computer. Trans Am Math Soc 199:1–28 · Zbl 0296.02022 |
| [44] | Rose HE (1984) Subrecursion: functions and Hierarchies. Clarendon Press, Oxford · Zbl 0539.03018 |
| [45] | Shannon CE (1941) Mathematical theory of the differential analyzer. J Math Phys MIT 20:337–354 · Zbl 0061.29410 |
| [46] | Turing A (1936) On computable numbers, with an application to the Entscheidungs problem. Proc Lond Math Soc 2(42):230–265, (correction ibid. 43:544–546, 1937). |
| [47] | Weihrauch K (2000) Computable analysis: an introduction, 1st edn. Springer, Berlin · Zbl 0956.68056 |
| [48] | Zhou Q (1997) Computing and combinatorics. In: Subclasses of computable real valued functions. Lecture Notes in Computer Science, vol 1276. Springer Berlin/Heidelberg, pp 156–165 · Zbl 0883.03047 |
| [49] | Zimmerman J (1990) Classes of Grzegorczyk’s-computable real numbers. PhD thesis, University of Minnesota |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
