Paradigmi di computazione per i numeri reali
Gherardi, Guido
La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana, Tome 1 (2008), p. 525-554 / Harvested from Biblioteca Digitale Italiana di Matematica
Access to full text
Full (PDF)
Full (DjVu)

In questo articolo trattiamo lo sviluppo storico del concetto di funzione reale computabile. Durante il XX secolo alcune scuole hanno proposto approcci alternativi alla questione, ma in generale tra loro strettamente correlati. Tuttavia, mettiamo in risalto come i due paradigmi TTE a real-RAM, traendo origine da due differenti rami della matematica (teoria della computabilità ed analisi numerica) abbiamo elaborato due approcci contrastanti.

In this paper we deal with the historical development of the notion of computable real function. During the XX century, some mathematical schools provided different approaches to the subject, which are in general strictly related. Nevertheless, we point out how the two paradigms TTE and real-RAM have formulated two incompatible approaches. This contrast is mainly due to their own two different theoretical foundations (computer science on the one hand and numerical analisis on the other).

Publié le : 2008-12-01
@article{RIUMI_2008_1_1_3_525_0,
     author = {Guido Gherardi},
     title = {Paradigmi di computazione per i numeri reali},
     journal = {La Matematica nella Societ\`a e nella Cultura. Rivista dell'Unione Matematica Italiana},
     volume = {1},
     year = {2008},
     pages = {525-554},
     mrnumber = {2500209},
     language = {it},
     url = {http://dml.mathdoc.fr/item/RIUMI_2008_1_1_3_525_0}
}

Gherardi, Guido. Paradigmi di computazione per i numeri reali. La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana, Tome 1 (2008) pp. 525-554. http://gdmltest.u-ga.fr/item/RIUMI_2008_1_1_3_525_0/

[1] Blum, L. - Cucker, F. - Schub, M. - Smale, S., Complexity and Real Computation. Springer (1998). | MR 1479636

[2] Brattka, V., Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly, 51 (2005), 19-44. | MR 2099383 | Zbl 1059.03074

[3] Braverman, M. - Cook, S., Computing over the Reals: Foundations for Scientific Computing. Notices of the American Mathematical Society, 53 (2005), 318-329. | MR 2208383 | Zbl 1092.68038

[4] Kechris, A., Classical Descriptive Set Theory. Springer (1995). | MR 1321597 | Zbl 0819.04002

[5] Kuratowski, K., Topology. Volume I. Academic Press (1966). | MR 217751

[6] Odifreddi, P., Classical Recursion Theory. North Holland (1989). | MR 982269 | Zbl 0661.03029

[7] Odifreddi, P., Classical Recursion Theory. Volume II. North Holland (1999). | MR 1718169 | Zbl 0931.03057

[8] Penrose, R., The Emperor's New Mind. Oxford University Press. 1989 (edizione italiana: La Mente Nuova dell'Imperatore. Rizzoli, 1992) | MR 1048125

[9] Pour-El, M. B. - Richards, J. I., Computability in Analysis and Physics. Springer (1989). | MR 1005942 | Zbl 0678.03027

[10] Turing, A., On computable real numbers, with an application to the "Entscheidungsproblem". Proceedings of the London Mathematical Society, 422 (1936), 230-265. | MR 1577030 | Zbl 62.1059.03

[11] Turing, A., On computable real numbers, with an application to the "Entscheidungsproblem". A correction. Proceedings of the London Mathematical Society, 432 (1937), 544-546. | MR 1575661 | Zbl 63.0823.02

[12] Turing, A., Rounding-off Errors in Matrix Processes. The Quarterly Journal of Mechanics and Applied Mathematics, 1 (1948), 287-308. | MR 28100 | Zbl 0033.28501

[13] Weihrauch, K., Computability. Springer (1987) | MR 892102

[14] Weihrauch, K.: Computable Analysis. Springer (2000). | MR 1795407 | Zbl 0956.68056

[15] Weihrauch, K. - Zhong, N., The Wave Propagator is Turing Computable, in J. Wiedermann P. Van Emde Boas - M. Nielsen (Eds.), Automata, Languages and Programming. Lecture Notes in Computer Science, 1644 (1999), 697-706. | MR 1731529 | Zbl 0945.03092