A Taxonomy of Computation and Information Architecture

ABSTRACT

This paper presents taxonomy of models of computation. It includes Existential (Physical, Abstract and Cognitive), Organizational, Temporal, Representational, Domain/Data, Operational, Process-oriented and Level-based taxonomy. It is connected to more general notion of natural computation, intrinsic to physical systems, and particularly to cognitive computation in living organisms and artificial cognitive systems. Computation is often understood through the Turing machine model, in the fields of computability, computational complexity and even as a basis for the present-day computer hardware and software architectures. However, several aspects of computation, even those existing in today's applications, are left outside in this model, thus adequate models of real-time, distributed, self-organized, resource-aware, adaptive, learning computation systems are currently being developed.

References

1. R. Landauer, "The Physical Nature of Information," Phys. Lett. A, vol. 217, p. 188, 1996.
2. J. Crutchfield, W. Ditto, and S. Sinha, "Introduction to Focus Issue: Intrinsic and Designed Computation: Information Processing in Dynamical Systems---Beyond the Digital Hegemony," Chaos, vol. 20, no. 037101, 2010.
3. A. M. Turing, "On computable numbers, with an application to the Entscheidungs problem," Proc. London Math. Soc., vol. 42, no. 42, pp. 230--265, 1936.
4. A. N. Kolmogorov, "On the Concept of Algorithm," Russ. Math. Surv., vol. 8, no. 4, pp. 175--176, 1953.
5. B. J. Copeland, "What is computation?," Synthese, vol. 108, no. 3, pp. 335--359, 1996.
6. M. Burgin, Super-Recursive Algorithms. New York: Springer-Verlag New York Inc., 2005.
7. P. Denning, "What is computation?: Editor's Introduction," Ubiquity, no. October, pp. 1--2, 2010.
8. M. Burgin and G. Dodig-Crnkovic, "Information and Computation -- Omnipresent and Pervasive," in Information and Computation, New York/London/Singapore: World Scientific Pub Co Inc, 2011, pp. vii --xxxii.
9. H. Zenil, A Computable Universe. Understanding Computation & Exploring Nature As Computation. Singapore: World Scientific Publishing Company/Imperial College Press, 2012.
10. C. Hewitt, "What is computation? Actor Model versus Turing's Model," in A Computable Universe, Understanding Computation & Exploring Nature As Computation, H. Zenil, Ed. World Scientific Publishing Company/Imperial College Press, 2012.
11. G. Dodig-Crnkovic, "Significance of Models of Computation from Turing Model to Natural Computation," Minds Mach., vol. 21, no. 2, pp. 301--322, 2011.
12. L. Fortnow, "The enduring legacy of the Turing machine," Comput. J., vol. 55, no. 7, pp. 830--831, 2012.
13. D. Goldin, S. Smolka, and P. Wegner, Eds., Interactive Computation: The New Paradigm. Berlin, Heidelberg: Springer, 2006.
14. J. S. Conery, "Computation is symbol manipulation," Comput. J., vol. 55, no. 7, pp. 814--816, 2012.
15. D. E. Angelaki, A. G. Shaikh, A. M. Green, and J. D. Dickman, "Neurons compute internal models of the physical laws of motion," Nature, vol. 430, no. 6999, pp. 560--564, 2004.
16. S. Abramsky, "Information, Processes and Games," in Philosophy of Information, J. Benthem van and P. Adriaans, Eds. Amsterdam, The Netherlands: North Holland, 2008, pp. 483--549.
17. R. Mikkilineni, "Going beyond Computation and Its Limits: Injecting Cognition into Computing," Appl. Math., vol. 3, pp. 1826--1835, 2012.
18. R. Mikkilineni, Designing a New Class of Distributed Systems, SpringerBr. Berlin Heidelberg: Springer, 2011.
19. M. Burgin and G. Dodig-Crnkovic, "Typologies of Computation and Computational Models," Arxiv.org, vol. arXiv:1312, 2013.
20. M. Burgin, Structural Reality. New York: Nova Science Publishers, 2012.
21. W. Bucci, Psychoanalysis and Cognitive Science: A Multiple Code Theory. New York: Guilford Press, 1997.
22. A. Clark, Microcognition: Philosophy, Cognitive Science, and Parallel Distributed Processing. Cambridge, MA: MIT Press, 1989.
23. N. Fresco, Physical Computation and Cognitive Science. Berlin Heidelberg: Springer Berlin Heidelberg, 2014.
24. M. Burgin and M. L. Smith, "Concurrent Composition and Algebras of Events, Actions, and Processes," arXiv:0803.3099, 2008.
25. O. Bournez, "Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy," Theor. Comput. Sci., vol. 210, pp. 210--211, 1977.
26. V. Gupta, R. Jagadeesan, and V. A. Saraswat, "Computing with continuous change," Sci. Comput. Program., vol. 30, no. 1-2, pp. 3--49, 1998.
27. C. Shannon, "Mathematical Theory of the Differential Analyzer," J. Math. Phys., vol. 20, pp. 337--354, 1941.
28. C. Moore, "Recursion theory on the reals and continuous-time computation," Theor. Comput. Sci., vol. 162, no. 1, pp. 23--44, 1996.
29. W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity. 1943.," Bull. Math. Biol., vol. 52, no. 1--2, pp. 99--115; discussion 73--97, 1990.
30. L. Blum, F. Cucker, M. Shub, and S. Smale, "Complexity and Real Computation: A Manifesto," Int. J. Bifurc. Chaos, vol. 6, no. 1, pp. 3--26, 1996.
31. M. Burgin and E. Eberbach, "Evolutionary Computation and Processes of Life," Ubiquity, no. August, pp. 1--13, 2012.
32. E. W. Dijkstra, "A Short Introduction to the Art of Computer Programming," 1971.
33. G. Dodig-Crnkovic and R. Giovagnoli, Computing Nature. Berlin Heidelberg: Springer, 2013.
34. G. Rozenberg, T. Bäck, and J. N. Kok, Eds., Handbook of Natural Computing. Berlin Heidelberg: Springer, 2012.
35. G. Rozenberg and L. Kari, "The many facets of natural computing," Commun. ACM, vol. 51, pp. 72--83, 2008.
36. S. Stepney, S. L. Braunstein, J. A. Clark, A. M. Tyrrell, A. Adamatzky, R. E. Smith, T. R. Addis, C. G. Johnson, J. Timmis, P. H. Welch, R. Milner, and D. Partridge, "Journeys in Non-Classical Computation I: A Grand Challenge for Computing Research," Int. J. Parallel Emerg. Distr. Syst., vol. 20, pp. 5--19, 2005.
37. S. Stepney, S. L. Braunstein, J. A. Clark, A. M. Tyrrell, A. Adamatzky, R. E. Smith, T. R. Addis, C. G. Johnson, J. Timmis, P. H. Welch, R. Milner, and D. Partridge, "Journeys in Non-Classical Computation II: Initial Journeys and Waypoints," Int. J. Parallel Emerg. Distr. Syst., vol. 21, pp. 97--125, 2006.
38. P. Denning, "Computing is a natural science," Commun. ACM, vol. 50, no. 7, pp. 13--18, 2007.
39. P. Denning and P. Rosenbloom, "The fourth great domain of science," ACM Commun., vol. 52, no. 9, pp. 27--29, 2009.
40. R. P. Feynman, "Simulating Physics with Computers," Int. J. Theor. Phys., vol. 21, no. 6/7, pp. 467--488, 1982.
41. M. Nadin, "Anticipatory Computing. From a High-Level Theory to Hybrid Computing Implementations," Int. J. Appl. Res. Inf. Technol. Comput., vol. 1, no. 1, pp. 1--27, 2010.
42. S. Stepney, "The neglected pillar of material computation," Phys. D Nonlinear Phenom., vol. 237, no. 9, pp. 1157--1164, 2008.
43. R. Brooks, "Elephants don't play chess," Rob. Auton. Syst., vol. 6, pp. 3--15, 1990.
44. S. B. Cooper, B. Löwe, and A. Sorbi, New Computational Paradigms. Changing Conceptions of What is Computable. Springer Mathematics of Computing series, XIII. Springer, 2008.
45. S. B. Cooper, "Turing's Titanic Machine?," Commun. ACM, vol. 55, no. 3, pp. 74--83, 2012.
46. S. B. Cooper, "How Can Nature Help Us Compute?," in SOFSEM 2006: Theory and Practice of Computer Science - 32nd Conference on Current Trends in Theory and Practice of Computer Science, 2006, pp. 1--13.
47. S. B. Cooper, "The Mathematician's Bias - and the Return to Embodied Computation," in A Computable Universe: Understanding and Exploring Nature as Computation, H. Zenil, Ed. World Scientific Pub Co Inc, 2012.
48. Y. Wang, "On Abstract Intelligence: Toward a Unifying Theory of Natural, Artificial, Machinable, and Computational Intelligence," Int. J. Softw. Sci. Comput. Intell., vol. 1, no. 1, pp. 1--17, 2009.
49. Y. Wang, "Toward a Formal Knowledge System Theory and Its Cognitive Informatics Foundations," in Transactions on Computational Science V, vol. 5540, M. L. Gavrilova, C. J. K. Tan, Y. Wang, and K. C. C. Chan, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 1--19.
50. Y. Wang, "On Contemporary Denotational Mathematics for Computational Intelligence," Trans. Comput. Sci., vol. 2, pp. 6--29, 2008.
51. Y. Wang, "The Theoretical Framework of Cognitive Informatics," Int'l J. Cogn. Informatics Nat. Intell., vol. 1, no. 1, pp. 1--27, 2007.
52. G. Dodig-Crnkovic and V. Mueller, "A Dialogue Concerning Two World Systems: Info-Computational vs. Mechanistic," World Scientific Pub Co Inc, Singapore, 2009.
53. G. Tononi, "The Integrated Information Theory of Consciousness: An Updated Account," Arch. Ital. Biol., vol. 150, no. 2/3, pp. 290--326, 2012.
54. H. Maturana, "Autopoiesis, Structural Coupling and Cognition: A history of these and other notions in the biology of cognition," Cybern. Hum. Knowing, vol. 9, no. 3--4, pp. 5--34, 2002.
55. H. Zenil, "Quantifying Natural and Artificial Intelligence in Robots and Natural Systems with an Algorithmic Behavioural Test," in Metrics of sensory motor integration in robots and animals, Cognitive., F. P. Bonsignorio, A. P. del Pobil, E. Messina, and J. Hallam, Eds. Berlin Heidelberg: Springer, 2015.
56. C. E. Maldonado and A. N. Gómez Cruz, "Biological hypercomputation: A new research problem in complexity theory," Complexity, vol. wileyonlin, no. 1099--0526, 2014.
57. C. E. Maldonado and A. N. Gómez Cruz, "Biological Hypercomputation: A Concept is Introduced," http://arxiv.org/pdf/1210.4819.pdf, 2012.
58. G. Dodig-Crnkovic, "Info-computational Constructivism and Cognition," Constr. Found., vol. 9, no. 2, pp. 223--231, 2014.
59. G. Dodig-Crnkovic, "Information, Computation, Cognition. Agency-based Hierarchies of Levels," arXiv:1311.0413, 2013.
60. G. Dodig-Crnkovic, "Modeling Life as Cognitive Info-Computation," in Computability in Europe 2014. LNCS, 2014, pp. 153--162.
61. A. C. Ehresmann, "A Mathematical Model for Info-computationalism," Constr. Found., vol. 9, no. 2, pp. 235--237, 2014.
62. G. Dodig-Crnkovic, "The Development of Models of Computation with Advances in Technology and Natural Sciences," in Symposium of The British Society for the Study of Artificial Intelligence, AISB 2013, 2013.
63. G. Dodig-Crnkovic, "Why we need info-computational constructivism," Constr. Found., vol. 9, no. 2, pp. 246--255, 2014.
64. D. C. Horsman, "Abstraction/Representation Theory for heterotic physical computing," Philos. Trans. R. Soc. London A Math. Phys. Eng. Sci., vol. 373, no. 2046, Jun. 2015.

Index Terms

• Computer systems organization

  • Architectures

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence