CSC 341: January 22, 2007

From CSWiki

1 Lecture
2 Study questions
- 2.1 Proposed Solutions
3 Discussion
4

Lecture

Algorithms and computability

You are already acquainted with the concept of an algorithm, that is, an exact method for solving any instance of a general, formally stated problem in a finite number of simple, effective steps, and you've learned many algorithms and many techniques for designing new ones. In this course, we move up one more level of abstraction and consider all possible algorithms and all possible computations. We shall find that different kinds of mechanisms for performing computations can implement different classes of algorithms, and that there are problems that can be formally stated but cannot be solved algorithmically at all. We shall study the form and nature of this unexpected limitation.

[edit]

Models of computation

We approach this subject through careful formal definitions and proofs. The theory of computation that we shall examine and develop is a mathematical theory. It begins with the construction of models of computation. Initially, these models may strike you as unrealistically simple. For instance, in one of these models, we shall consider a family of machines in which the only kind of instruction is "Inspect your current state and the symbol currently at the front of your input channel; using that symbol as a key, look up the appropriate successor state and enter it." This minuscule instruction set will not inconvenience us much, because we shall write only a few toy programs for such machines. The point of having such a simple model is to make it easier to prove theorems, at a higher level of abstraction, about which problems such machines can solve and which ones they cannot. That will provide us with a basis for considering how the extensions that convert simple machines into somewhat more realistic ones affect their ability to solve problems.

Altogether, we shall consider several models of computation. In the one that I have just described, each step in a computation is the execution of one machine instruction; we'll look at several variants of this model, featuring machines with different instruction sets and different input/output mechanisms. We shall also consider a model in which each step is a syntactic transformation performed on a string of symbols, erasing some and inserting others, and a functional model in which composition and recursion are used to combine simpler functions into more complex ones, and even a model in which the steps are dominoes with exotic marks on them, and the computation is a game in which these dominoes are aligned in specified ways.

Each of these models of computation provides an answer to the question of which problems can be solved by computation, and there are interesting relationships among these answers. We shall spend most of the semester exploring these relationships.

[edit]

Tractability

Among the problems for which algorithmic solutions exist, there are some that are not merely soluble but tractable, in the sense that the solution to any instance of the problem can be obtained in a number of steps that is bounded above by some polynomial function of the size of the input. In the last few weeks of the semester, we shall examine some of what little is known about the form and nature of the boundary enclosing the set of all tractable problems and look at one or two other ways of classifying problems of varying difficulty.

[edit]

Studying theory

Pursuing accurate answers to these questions demands of the student two character traits that are consistent but not always easy to reconcile: the creative intuition by which one perceives or discovers connections between ideas at a very abstract level, and the attention to detail by which one builds rigorous proofs that embody those connections. In this course, I shall help you to develop and exercise both of these traits and to find the right balance between them. Fortunately, these traits of creative intuition and attention to detail are also needed in computer programming, so computer-science majors are generally eager to develop them anyway.

For most of you, this will entail studying and doing homework problems in a somewhat different way than in other courses. The readings are mostly short, but they are unusually dense and abstract, and this is unavoidable given the subject matter. You may be tempted to skim them and turn to the exercises, going back to the text only as needed. This probably will not work, and you should resist the temptation. Instead, take extra time to re-read and think about each part of the reading. If you don't get it, formulate questions about it and have them ready for the next class session or for a visit to my office. It will be a good sign if, when you finish the reading and look at the exercises at the end of a chapter, you can understand right away what the exercise is asking, without going back into the chapter to look up the technical terms.

Many of the homework problems will involve constructing proofs, and I shall often point out and emphasize the similarities between this activity and the construction of computer programs. Proof structures are like program structures. There are design patterns for proofs as there are for programs. Modularity is an important notion in proof construction, where it is called "proving lemmas," as it is in programming. Using early theorems to help prove later ones is analogous to building code libraries to construct applications.

However, one difference between programming and proof construction poses a hazard even for experienced programmers: In proof construction, there is no compiler to keep you from making careless low-level mistakes. This means that you must be unusually careful in your formulation of proofs. It's more like the early days of computing, the days of Big Iron, before there were time-sharing systems, before processor time became cheap. In those days, the turn-around time between submitting the card deck on which your program was punched and receiving the printed output from your program from the operator was measured in hours, so that making a stupid syntax error in one line of your program could cost you half a day. As a result, programmers learned to take unusual care to avoid stupid syntax errors. In this course, similarly, you should plan to take unusual care to avoid careless mistakes in proof construction: double-checking and proofreading your work with a skeptical eye, making sure that you justify each non-trivial step.

[edit]

Chapter 0: Preliminaries

The assigned reading for Wednesday is chapter 0 of our principal textbook, ``Introduction to the theory of computation, by Michael Sipser. It briefly presents some basic definitions concerning sets, functions, and graphs. Since "Combinatorics" is a prerequisite for this course, I imagine that you have seen a lot of this material before, although the subsections called "Strings and languages" and "Boolean logic" introduce some terminology that may be new to you (so pay attention to them).

Chapter 0 also acquaints readers with the author's notational conventions, which are not necessarily exactly the same as those used in your combinatorics course.

The last section of chapter 0 deals with three specific forms of mathematical proof that we'll use occasionally during the course: proof by construction, proof by contradiction, and mathematical induction.

Many of the proofs that we shall encounter and construct in this course conform to a few common design patterns. Learn these patterns from the theorems that are proven either in the textbook or in class, and think about how to reimplement them in the related proofs that you are called on to construct.

One of the reasons that proof designs recur frequently in this courses is that the theorems that we'll prove tend to have the same form: A machine of this kind can solve this particular problem, but no machine of this other kind can do so. Machines of this kind can emulate machines of this other kind and so can solve any problem that machines of the other kind can solve. These two models of computation are equivalent, in the sense that any problem that can be solved under either model can be solved under both. Sometimes the proof of a proposition of one of these forms is long and tricky, but it will almost always be clear where we're headed.

[edit]

The cooperative commentary

Students who have taken this course from me in the past have sometimes reported feeling intimidated by the isolation in which they worked. No matter how much I praise the bracing, confidence-building opportunities for self-discovery and the development of intellectual stamina that the exercises in this course present, my policy against collaboration seems to be an obstacle for many students right at the outset.

For this reason, I looked around this time for ways to relieve this feeling of isolation, and I settled on the idea of having the class develop, over the course of the semester, a commentary on the assigned readings -- something that will help readers to understand the difficult parts and to put the basic ideas into a framework that might be more accessible than the one the author has chosen. Such a commentary might benefit future students who are assigned the same readings, and will incidentally help us to enlighten ourselves and confirm our own understanding of the subject.

As an experiment, I've chosen a wiki as the development medium for our commentary. This will have the incidental benefit of providing us all with some experience in collective expository writing and revision, which I expect to be increasingly common both in academia and in industry over the next few years. I'll talk more about our course wiki at our next meeting.

From my point of view, the experiment will have worked if, at the moment when you're looking blackly an exercise and have no idea how to get started with it, you can think to yourself, "I wonder whether there's something in the wiki that might help me out," and find enough comfort in the prospect to keep going. The obstacle is usually not so much the difficulty of the material as the combination of a steep learning curve with the crushing feeling of having to climb it entirely on one's own; my idea is that, through the wiki, you'll have the rest of the class at your back as you start the climb.

I still want to require that the solutions you submit reflect your own work, so collaboration on exercises is still prohibited, and that includes wiki-based collaboration: You may not post solutions or partial solutions to exercises on the wiki, or take solutions or partial solutions from the wiki (or from anywhere else on the Web) and turn them in. My hope is that being able to read and write as much as you like about the ideas underlying the exercises will suffice.

To encourage you to contribute to the cooperative commentary, I plan to base two-fifths of your grade in this course on your wiki work, considering both the amount and the quality of your contributions. I shall award credit both for good questions and for good answers, and both for adding new pages and topics and for improving existing pages and topics.

One problem with experiments like this is that they don't always work, and in a way I'm sorry to subject you folks to relatively untested pedagogy. I hope, therefore, that any of you who don't like the way it seems to be going will explain the weak points of the approach to me, perhaps by coming in during my office hours. Indeed, I hope that you'll feel comfortable stopping in at my office whenever you have something to say or to ask about the course. I'll listen carefully and do my best to address any difficulties you encounter.

[edit]

Study questions

Define the terms `algorithm' and `computation', making the relationship between these concepts clear.
What algorithm do you use to find the quotient and remainder when 207348 is divided by 417? What are the steps in this computation?
Judging from the examples in the lecture (above) and the history of the computer industry, models of computation seem to be quite varied in nature and limitless in number. Doesn't this imply that the theory of computation is similarly varied and limitless? How could one ever attain general knowledge about computation in this setting?
Since the exponent on a polynomial function can be arbitrarily large, why aren't all soluble problems tractable, in the sense defined in the lecture?

[edit]

Proposed Solutions

Dictionary.com defines algorithm as "a set of rules for solving a problem in a finite number of steps" and defines computation as "an act, process, or method of computing; calculation." An algorithm is more rigorously defined than a computation, as it must deal with every encounterable circumstance. Because of this a computation can change if it's given different parameters, whereas there is no corresponding chance in an algorithm.
There is no implication that we can't examine the theory of computation because there is nothing stopping us from making general or universally applicable observations about all of the individually varied models and theories of computation. We'll [hopefully] attain general knowledge about computation by making globally true observations about all the varied cases.
Some computations may use randomness that would prevent us from putting an upper bound on these problems. All soluble problems are not tractable because we can have a soluble problem with an order $x n$ running time, where $x > 1$ (or even running times greater than that) and the sense of tractability given in the lecture deals with order $n x$ running times only.