Sign In

Communications of the ACM

Communications of the ACM

What Is an Algorithm?


Communications Editor-in-Chief Moshe Y. Vardi

The 14th International Congress of Logic, Methodology and Philosophy of Science (CLMPS), held last July in France, included a special symposium on the subject of "What is an algorithm?"

This may seem to be a strange question to ask just before the Turing Centenary Year, which is now being celebrated by numerous events around the world (see http://www.turingcentenary.eu/). Didn't Turing answer this question decisively? Isn't the answer to the question "an algorithm is a Turing machine"?

But conflating algorithms with Turing machines is a misreading of Turing's 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Turing's aim was to define computability, not algorithms. His paper argued that every function on natural numbers that can be computed by a human computer (until the mid-1940s a computer was a person who computes) can also be computed by a Turing machine. There is no claim in the paper that Turing machines offer a general model for algorithms. (See S. B. Cooper's article on page 74 for a perspective on Turing's model of computation.) So the question posed by the special CLMPS symposium is an excellent one.

Incontrovertibly, algorithms constitute one of the central subjects of study in computer science. Should we not have by now a clear understanding of what an algorithm is? It is worth pointing out that mathematicians formalized the notion of proof only in the 20th century, even though they have been using proofs at that point for about 2,500 years. Analogously, the fact that we have an intuitive notion of what an algorithm is does not mean that we have a formal notion. For example, when should we say that two programs describe the same algorithm? This requires a rigorous definition!

Surprisingly, the two key speakers in the symposium, Y. Gurevich and Y. Moschovakis, provided very different answers to this basic question, even after focusing on classical sequential algorithms (see in-depth papers at http://goo.gl/0E7wa and http://goo.gl/HsQHq).

Gurevich argued that every algorithm can be defined in terms of an abstract state machine. Intuitively, an abstract state machine is a machine operating on states, which are arbitrary data structures. The key requirement is that one step of the machine can cause only a bounded local change on the state. This requirement corresponds both to the one-cell-at-a-time operations of a Turing machine and the bounded-width operations of von Neumann machines.


Is an algorithm an abstract state machine or a recursor?


Moschovakis, in contrast, argued that an algorithm is defined in terms of a recursor, which is a recursive description built on top of arbitrary operations taken as primitives. For example, the factorial function can be described recursively, using multiplication as a primitive algorithmic operation, while Euclid's greatest-common divisor algorithm can be described recursively, using the remainder function as a primitive operation.

So is an algorithm an abstract state machine or a recursor? Mathematically, one can show that recursors can model abstract state machines and abstract state machines can model recursors, but which definition is primary?

I find this debate reminiscent of the endless argument in computer science about the advantages and disadvantages of imperative and functional programming languages, going all the way back to Fortran and Lisp. Since this debate has never been settled and is unlikely to be ever settled, we learned to live with the coexistence of imperative and functional programming languages.

Physicists learned to live with de Broglie's wave-particle duality, which asserts that all particles exhibit both wave and particle properties. Furthermore, in quantum mechanics, classical concepts such as "particle" and "wave" fail to describe fully the behavior of quantum-scale objects. Perhaps it is time for us to adopt a similarly nuanced view of what an algorithm is.

An algorithm is both an abstract state machine and a recursor, and neither view by itself fully describes what an algorithm is. This algorithmic duality seems to be a fundamental principle of computer science.

Moshe Y. Vardi, EDITOR-IN-CHIEF


©2012 ACM  0001-0782/12/0300  $10.00

Permission to make digital or hard copies of part or all 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 full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.


Comments


Anonymous

Physics tries to describe the existing system of nature. The nature of light cannot be "stated by definition" as wave, nor as particle. State machines and recursors are mathematical definitions. Algorithm is also a concept, and, if not yet well defined, one can define it as he or she finds more convenient. This comparison seems nonsense to me.


Anonymous

Once again we have left it to the mathematicians to define a powerful computational concept using their language. These definitions are very limiting. Pray tell, how do the algorithms used by Nature fit in these definitions? Rather than defining such concepts as algorithm, computation and so on, a hopeless task at best, one should instead provide a list of examples of what constitutes an algorithm. This list will be forever incomplete, and that is a good thing. Incidentally, the very reason the Church-Turing Thesis is a "Thesis" and not a "Theorem" to this day, is precisely because no one can define "algorithm" or "computation". Had a definition existed the matter would have been settled, proving or disproving the conjecture. No one has tackled this task convincingly, and for a good reason.


Anonymous

Well, I believe it is possible to define an algorithm.
The central notion required is that of computable tasks.
(It is well defined in a series of papers written by Giorgi Japaridze.)

First of all, an algorithm is dependent on a chosen language L.
Hence, given a language L, an algorithm is a tuple where

O, written in L, is a list of agents (or a list of instructions)
of the form a1:T1, a2:T2, ... an:Tn where
each ai represents an agent that can perform some task Ti,

T, written in L, is a goal task that the computer must achieve
using O,

C is a computer which knows how to execute T given O, i.e,
which has the definition of the operational semantics of L.

Thus, O is an input to C and T is an output from C.

State machines and recursors, Java, C, Prolog, pseudocodes are languages where O, T
can perform only limited tasks. In other words, their expressiveness are
pretty limited. This causes some serious problems in expressing algorithms, including
lengthy codes.
(Some of these issues are discussed in
an article "relative algorithms: an agent-oriented declarative algorithms" written
by Keehang Kwon.

In conclusion, I think the best algorithm language is Japaridze's
Computability Logic (CL) because it is built on the notion of computable tasks.
The use of CL leads to versatile and concisely expressed algorithms.

In addition, I think the worst algorithm language is pseudocode, which is also the
most popular algorithm language. It leads to lengthy algorithms due to the lack of
nondeterminism.


Hassan Ait-Kaci

Algortihm ... Whence the word? ...
http://members.peak.org/~jeremy/calculators/alKwarizmi.html
http://en.khwarizmi.ir/khwarizmi.pdf

Computer Programming as an Art, Donald E. Knuth:
http://awards.acm.org/images/awards/140/articles/7143252.pdf


Jordi Planes

I must say beforehand I'm not a theoretician, so I might be inaccurate.

Since the beginning of computer science we have these two visions of an algorithm: Turing's vision (abstract state machine) and Church's vision (lambda calculus). I would add a third vision, Post's: string rewriting. We can see an algorithm as a sequence of rewriting rules.

Then, we have not a duality, but a trinity: iterative programming, functional programming and logic programming.

This idea links with one of the comments: we are in computer science, so not limited by physics. We are not describing a natural system, we create concepts. So, who knows, maybe somebody will create a new vision in the future.


CACM Administrator

The following letter was published in the Letters to the Editor in the June 2013 CACM (http://cacm.acm.org/magazines/2013/6/164592).
--CACM Administrator

Addressing the question "What Is an Algorithm?" in his Editor's Letter (Mar. 2012), Moshe Y. Vardi wrote that there is no consensus, suggesting the two abstract approaches of Yuri Gurevich(1) and Yiannis N. Moscovachis(2) were both correct; algorithms are the abstract state machines of Gurevich and the recursors of Moscovachis. This is (as Moscovachis said) like trying to explain that the number 2 is the set {, {}}, which is likely to leave an outsider less, not more, enlightened.

A proper definition would allow computer scientists to talk to the public about algorithms. The pragmatic motivation is to justify the treatment we informally apply to algorithms: construct, explain, and exchange; admire for elegance; debate whether one is the same as another; marvel that the one for the program Eliza is so simple; patent or sell them; or preclude protections based on principled argument. The theoretical motivation is to probe relationships to programs and abstract machines and promote discussion of semantics and implementation.

Now consider this definition: An algorithm is an abstract deterministic control structure accomplishing a given task under given conditions, expressed in a finite, imperative form. A critical look would reveal no formalities but plenty to consider, along with some surprises.

The definition includes compass-and-straight-edge algorithms (such as to bisect an angle) and other nonelectronic but straightforward sets of instructions. Excluded are recipes, which are not deterministic except in perversely rigorous cases. Also excluded are games, which, construed as a single agent's instructions, are not imperative control structures that accomplish a given task (with certainty) and which, construed as interchanges of moves, are not deterministic.

Perhaps most controversial, it also excludes recursive definitions, which are not imperative but declarative. A definition of the factorial function with a base case and a recursive case does not undertake a computation of a factorial or provide directions to do so. An algorithm must "do" not "be." (Gurevich noted that one possible algorithm generally available through such a definition starts with "Apply the equations..."; that is, the algorithm tells us the obvious thing to do with the definition.) The imperative requirement yields the interesting result that computers, at the hardware level, do not execute algorithms. Current flowing through circuits does not express an imperative. Algorithms are a human construct.

So, do all programs implement algorithms? People are the interpreters of the elements of the definition, responsible for measuring the concept against them. But how do we map the path from the human view to the mathematical view? Gurevich and Moscovachis each suggested the rich connotations of the concept of the algorithm cannot be captured fully through a recurrence relation or other set-theoretic object. We can honor their contributions by pursuing the questions raised by the definition I have outlined here or through a competing informal view.

Robin K. Hill
Laramie, WY

REFERENCES

(1) Gurevich, Y. What is an algorithm? Technical Report. Microsoft Research, Redmond, WA, 2011; http://research.microsoft.com/en-us/um/people/gurevich/Opera/209.pdf

(2) Moscovachis, Y.N. On founding the theory of algorithms. UCLA Department of Mathematics, Los Angeles, CA, 2002; http://www.math.ucla.edu/~ynm/papers/foundalg.pdf


CACM Administrator

The following letter was published in the Letters to the Editor in the July 2012 CACM (http://cacm.acm.org/magazines/2012/7/151227).
--CACM Administrator

Pondering Moshe Y. Vardi's Editor's Letter "What Is an Algorithm?" (Mar. 2012), one should consider the fact that in its most abstract and tangible form an algorithm is simply an integral number and that an interpretation of an algorithm as an abstract state machine reflects this truth. A researcher or engineer can then hypothesize other representations of the algorithm's number that might enhance computational efficiency.

One truly elegant notion supporting computational theory is that each of us can interpret a number's symbolic representation differently. Depending on which lens one uses, the view might reveal an integer, a floating-point value, a character in a collating sequence, or a computational behavior (such as function, procedure, or subroutine).

Likewise, one could take the view that an algorithm in its most abstract state is a complete collection of all the intangible thoughts and ideas that generate its design, whether based on lists of imperatives, nesting functions, states and transitions between them, transfer of tokens between containers in a Petri net, or any equivalent representation of a Turing machine. As such, an algorithm represents these ephemeral thoughts and ideas combined, ultimately resisting definitive and universal quantification and measurement.

To gain deeper insight into the abstractions surrounding a given algorithm, one would do well to also revisit earlier works on the topic. Pondering the original intent of the early visionaries of computing by republishing their work with critiques from today's leaders would be enlightening and enjoyable. As with many advances in science, their efforts were often met with stark criticism. However, reassessing their intent today could spark further refinement of modern concepts derived from computing's inherently iterative and optimizing research life cycle.

Jody Sharpe
Omaha, NE

-------------------------------------------

AUTHOR'S RESPONSE

A mathematical model tries to capture (abstractly) the essence of the phenomenon being modeled. From this perspective, a person saying, "What is an algorithm?" would not be satisfied with the answer "An algorithm is an integral number."

Moshe Y. Vardi
Editor-in-Chief


Displaying all 7 comments

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article