Materials on the Ontology of Algorithms

One good plan for a course on the ontology of algorithms would be to read the Editor's Letter from Moshe Vardi in the March 2012 issue of the Communications of the  ACM, "What is an Algorithm?" [1] A short up-to-date view from an authoritative source would start us off on the right foot.  Vardi reflects on the significance of his title question and the dearth of answers, and refers to two papers presented at an international congress by Yiannis Moschovakis and Yuri Gurevich.  We could spend a semester mastering the technical material and discussing the competing claims of those two works, deriving their implications, and comparing them with others.

But this is a junior class for newcomers to the fields.  A quick glance back at the course objectives fails to reveal "bafflement" or "intimidation."  It would be counter-productive to throw these students into the research literature of academic computer science.  Instead, we will start our exploration at the level of intuition and move forward into tutored intuition, perhaps approaching the same points across friendlier terrain.  Points raised by Moschovakis and Gurevich include the status of declarative structures as algorithms, for example, and the possibility that heterogeneous types of abstraction might be appropriate.  Nice issues!  All three papers are cited in the course textbook.

I am indeed writing a textbook for this course, which will end up as a modest textbooklet, or course packet.  I want to provide concise materials, encouraging students to contribute to the elaboration of questions as well as answers.  I want to easily reference other elements of the course, such as examples, tables, definitions, and completed exercises.  (The manuscript format is EPUB, using Amaya and Sigil for composition, and I will distribute the text for free to students.)

These written materials, unsurprisingly, are sparse.  Yet an outline emerges, built on a sequence of ontological questions.

• What is an algorithm, as defined by examples?
• What distinguishes algorithms from other abstract structures?
• What makes two algorithms identical or distinguishes one from another?
• What are the properties that we can attribute to individual algorithms?

I provide several simple algorithms on paper, to start, for close examination.  We will unapologetically use rigorous-enough pseudocode for the expression of algorithms.  We will gloss over implementation details and mathematical formalisms-- unless they arise naturally in some critical context.  We will spend a lot of time articulating descriptions of tasks and their solutions; we will not shrink from mundane or silly analogies if they help to get a concept across.

Such a breezy appeal to informality notwithstanding, this class calls for set theory and other simple discrete mathematics.  (Don't they all?)  The students will need to get comfortable with functions as sets of ordered pairs, and with Turing Machines as tangible abstractions (so to speak) for programs, and with uncomputable functions.  The resulting textbook's outline:

I.  Introduction
  In which we enact algorithms.

II.  The Background
  Definitions
    In which we tackle the definitions of philosophy, computer science, ontology, and algorithm, relying heavily on other people's work.
  Simple Set Theory
    In which we master the basics of finite and infinite sets and subsets, membership, operators, and cardinality.

III.  What Are Some Examples of Algorithms?
  In which we read, trace, and write pseudocode for standard named algorithms, trying to elicit possible characterizations.

IV.  What is the Class of Algorithms?
  In which we compare algorithms with other structures, such as directions, games, and proofs, and attempt to formulate some for simple tasks.

V.  What Makes Algorithms the Same or Different?
  In which we study programs as Turing Machines, as well as relations and functions, seeking insight to determine how many different payroll algorithms exist; not to mention, algorithms for trivial tasks, algorithms for arithmetic, and so forth.

VI.  What Properties do Algorithms Hold?
  In which we attempt to articulate the key properties that apply to all or some algorithms, or figure out why we can't.

Now that the course planning is under control, this blog may languish as I travel and finish preparations, until I get some time to report after the semester starts.


[1]  Moshe Vardi, What is an Algorithm?, Communications of the ACM, March 2012, pg. 5 (55:3) DOI:10.1145/2093548.2093549

Links to the two papers he mentions--
Gurevich:  http://goo.gl/0E7wa
Moschovakis: http://goo.gl/HsQHq