Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-08T06:36:09.508Z Has data issue: false hasContentIssue false
  • English
  • Français

Algorithmics and the Limits of Complexity

Published online by Cambridge University Press:  26 September 2008

Daniel Parrochia
Daniel Parrochia
Affiliation:
Faculty of PhilosohpyUniversity of Toulouse Le Mirail
Get access Rights & Permissions [Opens in a new window]

Abstract

Dagognet's work shows that making algorithmic compressions seems to be one of the major targets of scientific progress. This effort has been so successful that until recently one might have thought everything could be algorithmically compressed. Indeed, this statement, which might be seen as a scientific translation of the Hegelian thesis in its strong form (“the real is rational and the rational is real”), admits to some objective limits in computer science. Though a lot of algorithms are successful, there exist today, and perhaps forever, logical and physical limits that cannot allow us to cherish the dream of a “theory of everything.” Moreover, a complete mastery of complexity does not seem possible — because some domains of reality are too complicated to be computable, because the human brain is too limited, because computers cannot do that much better than the human brain, and because, ultimately, there are some kinds of things it would make no sense to compress. This paper shows that Dagognet's work came to recognize what a glance at the history of algorithmics has made evident.

Type
Article
Information
Science in Context , Volume 9 , Issue 1 , Spring 1996 , pp. 39 - 56
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aho, A. V., Hopcroft, J. E., and Ullman, J. D.. 1983. Data structures and Algorithms Reading, Mass; Addison-wesley.Google Scholar
Barrow, J. D. 1991. Theories of Everything. Oxford: Clarendon Press.Google Scholar
Baudrillard, J. 1976 L'échange symbolique et la mort. Paris Gallimard.Google Scholar
Bennett, C. A. 1982. “The Thermodyamics of Computation — A Review”. International Journal of Theoretical Physics 21 (12) (December): 905–40.CrossRefGoogle Scholar
Benvéniste, A., Métivier, M., and Priouret, P.. 1990. Adaptative Algorithms and Stochastic Approximations. Berlin: Springer Verlag.CrossRefGoogle Scholar
Boehm, Barry W., and Corrado, Giuseppe Jacopini. 1966. “Flow Diagrams, Turing Machines and Languaes with only Two Formation Rules.” Communication of the the ACM 9: 366–71.CrossRefGoogle Scholar
Bürckert, H. J., Herold, A., and schmidt-schauss, M.. 1990. “On Equational Theories.Unification and (Un) decidability.” In Unification, ed. Kirchner, C.. London: Academic Press.Google Scholar
Camus, A. 1968. Le mythe de Sisyphe. Paris Folio.Google Scholar
Chaitin, G. 1986. “Information Theoretic Computational Complexity.” In New Directions in the philosophy of Mathematics, ed. Tymocszko, T., pp. 289–99. Birkhaüser: Boston Inc.Google Scholar
Cherbonneau, B., et al. 1975a. Programmation Structurée, rapport n0 112. Toulouse: Université Paul Sabatier (UER d'Informatique).Google Scholar
Cherbonneau, B. 1975b. Développement d'un projet en programmation structurée, rapport n0 113. Toulouse: Université Paul Sabatier (UER d'Informatique).Google Scholar
Dagognet, F. 1969. Tableaux et langages de la chimie. Paris: Seuil.Google Scholar
Dagognet, F. 1970. Le Catalogue de la vie Paris: Galien.Google Scholar
Dagognet, F. 1975. Mémoire pourl l'avenir. Vers une méthodologie del'informatique. Paris Vrin.Google Scholar
Dagognet, F. 1984. Le Nombre et le Lieu. Paris: Vrin.Google Scholar
Dagognet, F. 1990. Nature. Paris: Vrin.Google Scholar
Dantzig, G. B. 1990. “Origins of Simplex Method.” In A History of Scientific Computing, ed. Nash, S.. Reading, Mass.: Addison-wesley.Google Scholar
Derevitskii, D. P., Fradkov, A. L. 1974. “Two Models for Analyzing the Dynamics of Adaptation Algorithms.” Automation and Remote Control 35 (1): 59–67.Google Scholar
Dijkstra, Edsger W. 1972 “Notes on Structured Programming.” in Structured Programming, ed. Dahl, O. J., Dijkstra, E. W., and Hoare, C. A. R, pp. 1–81. London: Academic Press.Google Scholar
Dijkstra, Edsger W. 1976. A Discipline of Programming. Englewood Cliffs, N.J.; Prentice-Hall.Google Scholar
Dijkstra, Edsger W., and Maurice, V. Wikes. 1968. “GOTO Statement Considered Harmful.” Communication of the ACM (Association for Computing Machinery) 11 (3) (March): 147–158.CrossRefGoogle Scholar
Edmonds, J. 1965. “Paths, Trees, and Flowers.” Canadian Journal of Mathematics 17: 449–67.CrossRefGoogle Scholar
Einstein, A. 1969. La Relativité, trans. Payot.Google Scholar
Fredkin, E., and Toffoli, T. 1982. “Conservative Logic.” International Journal of Theoretical Physics 21 (3–4) (04): 219–53.CrossRefGoogle Scholar
Gondran, M., and Minoux, M. 1979. Graphes et algorithmes. Paris: Eyrolles.Google Scholar
Hoare, C. A. R. 1969. “An Axiomatic Basis for Computer Programming.” Communication of the ACM 12 (10) (10, 03): 576–82.CrossRefGoogle Scholar
Khas'minskii, R. Z. 1966. “On Stochastic Processes Defined by Differential Equations with a Smaller Parameter.” Theory of Probability and Its Applications 11 (2): 211–28.CrossRefGoogle Scholar
Knuth, D. E. 1968. The Art of Computer Programming, vol.3, Soring and searching. Reading, Mass: Addison-Wesley.Google Scholar
Kushner, H. J., Huang, H. 1979. “Rates of convergence for Stochastic Approximation Type of Algorithms.” SIAM Journal Control and Opt. 17 (1): 607–17.CrossRefGoogle Scholar
Landauer, R. 1985. “Fundamental Physical Limitations of the Computational Process.” Annals of the New York Academy of Science 426: 161–70.CrossRefGoogle Scholar
Laurière, J.-L. 1986. Intelligence artificielle, résolution de problèmes par l'homme et la machine, vol. 1. Paris: Eyrolles.Google Scholar
McCarthy, J., et al. 1962. LISP 1.5 Programmer' Manual. Cambridge, Mass.: M.I.T. Press.CrossRefGoogle Scholar
Meyer, B., and Baudouin, C. 1980. Méthodes de programmation. Paris: Eyrolles.Google Scholar
Parrochia, D. 1991. Mathématiques et existence. Seyssel: Champ Vallon.Google Scholar
Parrochia, D. 1994. Cosmologie de l'information. Press: Hermès.Google Scholar
Pfeifer, R., Schreter, Z., and Steels, L. 1989. Connectionism in Perspective. Amsterdam: North Holland.Google Scholar
Poundstone, W. 1987. The Recursive Universe. Oxford: University Press.Google Scholar
Pratt, Terence W. 1976. A New Approach to Software Desigh, Implementation and Documentation.Google Scholar
Robbins, H. and Monro, S. 1951. “A Stochastic Approximation Method.” Ann Math Stat. 22: 400–407.CrossRefGoogle Scholar
Siekmann, Jörg H. 1990. “Unification Theorey.” In Unification, ed. Kirchner, C.. London: Academic Press.Google Scholar
Siklossy, L. 1976. Let' Talk LISP. Englewood Cliffs, N.J.: Prentice Hall.Google Scholar
Stockmeyer, M. 1973. “Word Problem Requiring Exponential Time,” 5th ACM SIGACT.CrossRefGoogle Scholar
Wilkes, Maurice V. 1968. “The Outer and Inner Syntax of a Programming Language.” The Computer Journal (March).CrossRefGoogle Scholar