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

Assignments and Activities on Algorithms

The student background is assumed to be mixed, some more comfortable with philosophy, and some, with computer science.  Assignments should be designed to both pull and push, so to speak.  And, as mentioned in "Pedagogical Goals," they should foster respect for the methods and matters of the other discipline.

Some assignments should be small.  Some should be large.  Some should be machine-gradable.  Some should be peer-gradable.  Some should be collaborative.  Some should require revision.  I intend to assign many short written pieces and many small research tasks.  Often, these will be combined.  Some will be assigned to only one person, who will have the duty of reporting to the class.  The instructor's task, in addition to formulating the assignments themselves, is to coordinate all of the work, and spread it fairly across the student body.

Initial work will focus on defining the concepts concerned-- philosophy, computer science, ontology, and algorithm-- that last, at least tentatively.  Subsequent early activities will exercise our grasp of particular algorithms in order to strengthen our understanding of the general abstract concept.  We will start by running through some simple classic algorithms for searching and sorting.  We will act out some of them with tangible data such as decks of playing cards, sorting the cards into order in different ways, and searching for target values in the deck in different ways. 

Questions that we will consider as we do so include:  How does this algorithm work; how would you explain it in a sentence?  What are the preconditions?  How is the output or solution manifested?  What makes this algorithm unique?  Worthy of a name?  Interesting?  The first few questions are more technical to appeal to the budding computer scientists, and the latter more lyrical, if you will, to appeal to the budding philosophers.  These questions can be turned into short assignments.

We will also watch carefully for steps in which we exercise human judgment or short cuts, and consider whether those can be captured in a program.  To clarify such issues, we will examine common sets of directions such as recipes, licensing procedures, and IRS tax form instructions.  We will consider whether computation is always a component of an algorithm, whether an algorithm can have intermediate input, and whether an algorithm assumes a problem to be solved.  While these preliminary questions lend themselves better to discussion than to individual writing, the writing can be assigned as a product of the discussion.

Short pointed work is effective, in my experience.  I rely on assignments of the fill-in-the-blank and worksheet type, which can serve as homework exercises with clear right and wrong answers [1].  And it doesn't have to be rote.  I can illustrate this in terms of another computer science topic, the Halting Problem, as it might be pitched to different levels of expectation.  A graduate level exercise on the Halting Problem might ask for a proof of its unsolvability and discussion of the implications.  An upper-division undergraduate form of the exercise might present a sketch of the proof and ask for its completion.  A lower-division undergraduate version (which I have used in a multi-disciplinary sophomore course) might supply each of the steps, written out, and ask for them to be arranged in the right order.  These techniques can be applied to explication of algorithms.  For this class, written traces of the more sophisticated sorting and searching algorithms might fill the bill, especially if they also require comments on the appropriate context of application.  If this doesn't quite work, subsequent problem sets can be pitched up or down.

Students will also perform Internet research to find algorithms in pseudocode form, and will send messages of acknowledgement to those who provide such materials.  We will build up expertise, and refine definitions, as we go along, so I will also assign students to record notes in class meetings, and post them in a repository for future reference.

For assignments directed to a higher level of thinking, I plan a project that probes how strictly algorithms are embedded in daily human or natural life, as mentioned in the previous post, "Theme: The Ontology of Algorithms."  This will require students to research, understand, and apply an algorithm in a familiar context, perhaps with some fictional or creative component, and will contribute to the investigation of some of the greater questions, such as whether nature executes algorithms.

We won't neglect assignments at the top levels of Bloom's taxonomy.  The students will (perhaps later) consider a couple of wild cards that might make juicy essay topics: 
(1) What would a non-analytic account of algorithms look like; how would this come out in the tradition of Continental philosophy? 
(2) Are algorithms created or discovered?
Question 2 seems a good candidate for an essay during the first half of the course that is later revised near the end, not with a view to correction of the answer, but with a view to more sophisticated treatment.

[1]  Mark Guzdial, BLOG@CACM, February 20, 2012, "Why Don't we use Worksheets in Computer Science Education?", http://cacm.acm.org/blogs/blog-cacm/146183-why-dont-we-use-worksheets-in-computer-science-education/fulltext

Theme: The Ontology of Algorithms

The theme that I have chosen for Fall 2012 is "The Ontology of Algorithms."  We can try to figure out the nature of the algorithm and what distinguishes it as a concept, what attributes algorithms might have, and what other questions might bear on the subject.  We can start with the idea of computations, as grasped formally and informally, and consider each of the elements input, process, and output.  We can consider such notions as whether nature executes algorithms. 

This will produce some questions for student discussion:
Will we require an algorithm to take input?  Will we require an algorithm to have output?  Are there different algorithms for the same function?  (Of course.)  Are there different functions for the same algorithm?  Hmm... that would require interpreting the actions of an algorithm as producing more than one set of ordered pairs.  Are there different programs for the same algorithm?  (Of course.)  Are there different algorithms for the same program?  That depends on the answer to the question whether there are different functions for a single algorithm.  Shall we detach the notion of algorithm from its theoretical base, the computation of a function?  Suppose we see systems all around us that do nothing; should we consider that the same as computing the identity function or the null result? 
Based on the question above about nature:  Does an algorithm have to be executed?  Does a seed embody an algorithm?  Is an algorithm a static program or a dynamic process, or both?

A good place to start might be some questions embedded in daily life:
Do we ourselves follow algorithms as we know them?  In the non-digital domain, do we practice or experience transmission protocols, LIFO versus FIFO processing sequences, semaphores, public keys, dangling pointers, caching...?  Is there a human analogue to algorithmic self-reference?  What about static data structures: Can we name a foundational set of data structures, provide identity conditions, and find analogues in human life?  Or are data structures inextricably integrated with algorithms?  What about a foundational set, and human analogues, of algorithmic errors? 

Some of these can become assignments, in some form.  As with all teaching, the challenge will be capture these topics in solid pedagogical elements such as student work, purposeful discussion, and meaningful assessments.

Pedagogical Goals

What are the objectives of the course?  In my case, I want to bring together two formidable disciplines into a junior-level one-semester course, the students in which will be required to have minimal experience in academic philosophy and computer science-- to wit, an introductory course in each.  For this subject, there is no standardized test for assessment.  That context informs my high-level list of course objectives, quite spare, which can be summed up as (1) to assimilate, and (2) to explore:

1. To master a grounding body of knowledge and an appreciative curiosity about the philosophy of computer science, to the extent of cogent explanation to others.

2. To build respect for both disciplines, especially in students from the other; to promote pride and concomitant rigor in the student's own discipline.

In other words, for objective 1, I will be happy if the students can explain the subject matter (algorithms in general, and a few in particular), and can also produce some reasonably substantial and accurate answers, in real time, when their friends ask, "Dude, what was that class about?"  This is a modest goal.  Flights of fancy would embrace serious scholarly work in the field, and even the refinement of the subject matter of the Philosophy of Computer Science itself...  As for objective 2, like all instructors, I want to bring about the kind of transformative contemplation that helps cultivate a breadth of wisdom and keenness of intellect in my students. 

Besides the large goals, it's time for a few preliminary methodological goals to serve as the means to the general ends.

I want to provide concise but thought-provoking materials, encouraging students to contribute to formulation of texts, questions, and answers.  I want to integrate the materials via regular references to elements of the course elsewhere, such as examples, tables, definitions, and past exercises.
I want to replace vague undirected blather with pointed and disciplined inquiry-- even if speculative-- and exposition.  I want to traverse a clear path through the materials-- even if selective-- that fosters "deep thinking."  I want assignments that give the students something meaningful to do, large enough for challenge and small enough for achievement, that delivers a worthwhile outcome.

Note that the objectives listed are independent of the theme, but it is meant to be inserted firmly into the placeholder "grounding body of knowledge" in objective 1.  Even though my position in a faculty development center favors me with revolutionary educational theories of all stripes, I hold a traditional view of content:  There should be some.

In fact, there should be plenty.  Scoping and circumscription of the appropriate body of knowledge, focused on the theme chosen, will be an initial challenge of this new course in this new subject.

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.