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

The Subject Matter

The field is inchoate.  The questions are disparate.  No syllabus synthesized from long tradition is available.  We need a focus, a jumping-off point.

Many working at an intersections of philosophy and computer science would assume that the proper subject matter of a course in the Philosophy of Computer Science is thinking machines-- that is, artificial intelligence (general AI), philosophy of mind, and epistemology, enjoying the light shed on these matters in this Turing Centenary year.  Indeed, this would be an appropriate theme.

The article entitled "Philosophy of Computer Science" in the Stanford Encyclopedia of Philosophy, by Turner and Eden [1], starts with a nice list of questions, and discusses mostly those issues concerned with programs-- semantics, specification-implementation-verification, and behavior.  Indeed, these would also be appropriate themes.

Issues regarding standards and licensing for the professions of computer science and software engineering give rise to interesting ethical questions, including the rights and responsibilities of the programmer; these also probe the relationship of computer science to other professions.  Data collection raises issues of privacy and security. And these too would be appropriate themes.

My dissertation adviser, Bill Rapaport, of the University at Buffalo, taught an undergrad/grad course on "Philosophy of Computer Science" [2], covering classic questions, and I myself taught a sophomore cross-disciplinary course called "Qualities of Quantities," centering on discrete math topics and computability.  Oxford University offers a new degree in "Computer Science and Philosophy" for either a bachelor's or master's, rooted in the mathematical intersection.  I see others worthy of investigation, as well, in the form of individual courses, conferences, talks, and papers.  

Although some precedents do exist, none exactly fill the bill.  I seek to draw out questions that are fresh, vivid, and approachable by undergraduates.  To expand the possible subject matter before selecting a theme, let's ask how else the traditional concerns of philosophy play out in computer science.

Computer Science Adaptation of Traditional Philosophical Concern: Aesthetics

Is computer science ugly?  Sterile?  Why do mechanistic procedures, which block emotional manipulation and influence, scare people?  What does steampunk tell us about the aesthetics of computation?  Or of technology?  How about the visions of technology presented by classical science fiction?  Does the beauty of mathematics encompass the beauty of computer science?  Are there any good computer science jokes?  What makes an algorithm "elegant"?  What makes computer scientists "geeky"? 

Computer Science Adaptation of Traditional Philosophical Concern: Metaphysics

Is computation the same as technology?  What is the space, in the realms of technology, or mechanistic devices, that is occupied by computation?  Is it exhaustive; is the universe a computer?  How do we tell?  What does it mean to be a computer?  Does everything that shows cause and effect, or inputs and outputs, or changed states, like the wind, like organic growth, compute?  What sort of object is a program?  What sort of object is an algorithm? Is the ontology of algorithms (or programs) like the ontology of theorems (or proofs) in mathematics?

Computer Science Interpretation of Traditional Philosophical Concern: Ethics

Does transfer from paper to electronic forms affect our view of data and its proper treatment; to what extent is our view of the proper treatment of data influenced by the limitations of the paper medium?   Is computing a resource, like others, that should be deployed judiciously, and otherwise conserved?  In addition to the privacy questions regarding data collection, who is responsible for that data's accuracy, maintenance over time, dissemination for the public good, and archiving?  Can data be owned?  Can an idea be owned?  Can its tangible forms be owned?  What are the tangible forms?  Does computing have a universal purpose?  Should it?  What is the effect of heavy venture-capital funding directed to the entertainment and marketing applications of computer science?  When posterity looks back at this early Information Age, will they think that we did something terribly wrong, and if so, what? 


[1] Turner, Raymond and Eden, Amnon, "The Philosophy of Computer Science", The Stanford Encyclopedia of Philosophy (Winter 2011 Edition), Edward N. Zalta (ed.), URL = <http://plato.stanford.edu/archives/win2011/entries/computer-science/>.

[2]  Rapaport, William F., "What is the Philosophy of Computer Science?", Website, URL = <http://www.cse.buffalo.edu/~rapaport/584/whatisphilcs.html>.

The Task and the Plan

In the Fall 2012 semester, I will teach "Introduction to the Philosophy of Computer Science" as a junior-level course at the University of Wyoming in the United States.  Not only is this a new course on this campus, but it's a new field in the academy.  After many years of teaching computer science, and several teaching logic in our Philosophy department, I now coordinate instructional computing at our Center for Teaching and Learning.  I hope my expertise in these roles aids development of worthwhile content and successful delivery. 

While this material is discipline-specific, even esoteric, I believe that its crossover nature, and aspects that lend themselves to general discussion of pedagogy, would appeal to a broad sector of academic readers.   I hope to offer most of my ideas during this summer of 2012, in order to have the major course design done before classes start at the end of August.  You are invited to follow along and contribute your own thoughts.  Identification will be required.  I will monitor posts and delete those that are incoherent, offensive, or otherwise counter-productive.

Here follow some of the facets that I hope to address, in concert with contributors:

1. The subject matter
2. Pedagogical goals, general and specific
3. Assignments that work
4. Teaching methods 

Please join in.  You may e-mail me a comment to post if you prefer not to set up a Google (or OpenID) account.