acm - an acm publication


Ubiquity symposium 'What is computation?'
Computation and information

Ubiquity, Volume 2010 Issue December, December 2010 | BY Ruzena Bajcsy 


Full citation in the ACM Digital Library  | PDF

In this sixth article in the ACM Ubiquity symposium,What is Computation? Ruzena Bajcsy of the University of California-Berkeley explains that computation can be seen as a transformation or function of information.

Computation is a transformation/function applied to information.

In order to answer the question, "What is computation?", I will rephrase it to "What is Information?"

Information is not only a reflection of reality, such as physical measurements and/or observations, but it can also be synthetic concepts invented by humans as they occur for example, in mathematics.

There are many examples of both types of information and their corresponding computation. While the history of differential and integral calculus goes back to the ancient times, the development of it came from the need to explain celestial mechanics.

On the other hand, Riemannian geometry came about as purely mathematical exercise, almost in protest to Euclidean geometry, which only later found applications such as relativity theory and how to compare different complex shapes.

L. Euler in 1736 was the first who introduced concept of graph theory motivated by his observation of the seven bridges of Knigsberg. Today we use graphs for many artificial intelligence problems, but we also study their complexity properties.

It should be rather clear to the reader the type of computation will be determined by the representation of the information. Hence computation with analytical functions will be very different than finding isomorphism or homomorphism.

The above computations are implicit as oppose to explicit.

Implicit computation is requires to solve a concurrent computation of the function, or of an equation. Explicit computation is iterative and/or recursive.

A good example of such computation is computing N! (n factorial) or Fibonacci numbers.

A convenient mental model of recursion defines the recursive object (whether that object is an equation, an algorithm, an image, or a rule) in terms of "previously defined" objects of the same class.

Finally, we need to clarify the concept of algorithm as a computational method/mechanisms...

The history of algorithms goes to 9th century Persian mathematician Abu Abdullah Muhammad ibn Musa Al-Khwarizmi. The word stands for all definite procedures that solves problem or perform some tasks. Turing 1936 formalized the concept by introducing Turing machine, which is the foundation of all sequential computing.

There is a class of problems that cannot be computed implicitly, such as decision making, but only algorithmically.

So what is computation?

It depends on the representation of the information upon which the computation has to be performed but also on the given task. Algorithmic computation is most general since it includes implicit, explicit, recursive computation, and decision making.

About the Author

Ruzena Bajcsy, is Director of CITRIS and Professor of Electrical Engineering and Computer Sciences at the University of California-Berkeley. Her research interests include tele-immersive environments, computer vision, AI, robotics, and sensor networks.


DOI: 10.1145/1895419.1899473


©2010 ACM     $10.00

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.


Leave this field empty

2018 Symposia

Ubiquity symposium is an organized debate around a proposition or point of view. It is a means to explore a complex issue from multiple perspectives. An early example of a symposium on teaching computer science appeared in Communications of the ACM (December 1989).

To organize a symposium, please read our guidelines.


Ubiquity Symposium: Big Data

Table of Contents

  1. Big Data, Digitization, and Social Change (Opening Statement) by Jeffrey Johnson, Peter Denning, David Sousa-Rodrigues, Kemal A. Delic
  2. Big Data and the Attention Economy by Bernardo A. Huberman
  3. Big Data for Social Science Research by Mark Birkin
  4. Technology and Business Challenges of Big Data in the Digital Economy by Dave Penkler
  5. High Performance Synthetic Information Environments: An integrating architecture in the age of pervasive data and computing By Christopher L. Barrett, Jeffery Johnson, and Madhav Marathe
  6. Developing an Open Source "Big Data" Cognitive Computing Platform by Michael Kowolenko and Mladen Vouk
  7. When Good Machine Learning Leads to Bad Cyber Security by Tegjyot Singh Sethi and Mehmed Kantardzic
  8. Corporate Security is a Big Data Problem by Louisa Saunier and Kemal Delic
  9. Big Data: Business, technology, education, and science by Jeffrey Johnson, Luca Tesei, Marco Piangerelli, Emanuela Merelli, Riccardo Paci, Nenad Stojanovic, Paulo Leitão, José Barbosa, and Marco Amador
  10. Big Data or Big Brother? That is the question now (Closing Statement) by Jeffrey Johnson, Peter Denning, David Sousa-Rodrigues, Kemal A. Delic