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?

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

I look forward to reading the textbook you're preparing. The more you describe the goals of the course the more I become more interested in it :-) Please consider me as one of your students(long distance).

ReplyDeleteHello, Liliana! Glad to hear it. I will post a more detailed outline of the textbook in due time, although I'm not sure that it will be suitable for public scruntiny this fall.

DeleteI'd welcome notices of other similar attempts, and I know that Bill Rapaport is developing a graduate-level textbook on this subject.