Philosophy of Computer Science: Online Resources

Position Paper #2:

What Is Computation?

Assignment

The Argument

1. Knuth, D.E. (1973). The Art of Computer Programming, Second Edition. Addison-Wesley, Reading, MA, pp. 4–6, characterizes the informal, intuitive notion of "algorithm" as follows:

   Although this premise is Knuth's explication of 'algorithm', the rest of this argument is mine, not his.

   1. "Finiteness. An algorithm must always terminate after a finite number of steps …"

   2. "Definiteness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case …"

   3. "Input. An algorithm has zero or more inputs …"

   4. "Output. An algorithm has one or more outputs …"

   5. "Effectiveness. [A]ll of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a [hu]man using pencil and paper …"

   Note: We can also say that A is an algorithm for computing a function f means that A is an algorithm as characterized above and that, for any input i, A's output for i = f's output for i; that is, for any i, A(i) = f(i).

2. Computer programming languages (like Java, Lisp, Fortran, etc.) are formal languages for expressing (or "implementing") algorithms.

3. Every computer programming language is equivalent in expressibility to a Turing Machine programming language.
   1. That is, every program in any programming language can be translated into the language for programming Turing Machines, and vice versa.

   2. That is, any function that is computable by any programming language is computable by a Turing Machine, and vice versa.

4. Some real computer programs violate parts of Knuth's definition:
   1. Airline-reservation systems, ATMs, operating systems, etc., never terminate.

   2. Heuristic AI programs don't always compute exactly the function that they were written for, but only come very close (see §5.6 of the book).

   3. The "effectiveness" of "mundane" or everyday procedures (like recipes) may depend on the environment in which they are executed.
      • For example, using a different brand of some ingredient can ruin a recipe, or one chef's "pinch" of salt might be another's 1/8th teaspoon. And can you really execute a recipe "using pencil and paper"?

   4. Algorithms can apparently be written that can perform an infinite computation in a finite amount of time (by continually accelerating).
      • For example, we can sum the terms of an infinite sequence in a finite amount of time if we take 1/(2^n) second to add the nth term.

   And so on.

5. Therefore, these programs (that is, the "real programs" referred to in premise 4 do not implement Turing Machines (contrary to premise 3).

6. Therefore, they (that is, the "real programs" referred to in premise 4 are not computable. (But how can a real computer program not be computable?!)

Argument Analysis

1. To evaluate this argument, you must state whether the argument is valid, and you must state whether and why you agree or disagree with each premise and conclusion.
   • If it is valid, and if you agree with each premise, then you believe that the argument is sound.
   • You are logically obligated to believe the conclusions of sound arguments!

     So, if you ever come across an argument that you think is sound, but whose conclusion you don't believe, then either:

     • one (or more) of the premises is false,
     • or the argument is invalid (that is, there is some way for the premises to be true yet for the conclusion to be false),
     • or both.

   To determine whether it is valid, you must suppose "for the sake of the argument" that all the premises are true, and then consider whether the conclusions logically follow from them.

   (Or: Can you imagine some way the world might be so that the premises are true but the conclusion is false?)

   Note that, in this argument, there are two conclusions: conclusion 5 and conclusion 6.

   So, do you agree that conclusion 5 follows logically from premise 1– premise 4 and/or that conclusion 6 follows logically from conclusion 5?
   If not, are there missing premises that are needed to make the argument(s) valid?
   If there are, do you agree with them (why/why not)?

2. Next, you must evaluate each premise. Do you agree with it? Why or why not?

3. Finally, do you agree with the conclusion(s)?
   You might agree with a conclusion because you think that the argument is sound;
   • if so, say so.

   Or you might think that there's something wrong with the argument but agree with the conclusion anyway;

   • if so, then try to present a better argument for the conclusion.

   Or you might not agree with the conclusion(s);

   • if not, state why, and try to give an argument for what you do believe.

Ground Rules

1. Your position paper should be approximately 1–2 typed pages, double-spaced (that is, about 250–500 words), and single-sided.

2. Please bring 5 copies to lecture on the due date.

3. At the top of the first page, please put the following information:
   1. the title "Position Paper #2"
   2. your name
   3. the course you are enrolled in
   4. the due date.

4. For general assistance with writing (including a suggested method of paper preparation and format, as well as advice on grammar), see my website, "How to Write".

   As before, this doesn't have to be a beautifully written essay with an abstract. You should just plunge in and evaluate the argument.

   But you do need to give full citations to any sources that you cite.

Suggestions and Guidelines for Peer-Group Editing

1. When you get into your small groups, introduce yourselves quickly, and share copies of your papers with each other.

2. Choose one paper to discuss first. (Suggestion: Go in alphabetical order by family name.)

3. After spending about 10–15 minutes on the first paper, move on to the next, going back to step 2, above, changing roles.

   Spend no more than 15 minutes per paper (because you've only got about 45 minutes at most).

   Perhaps one member of the group can be a timekeeper.

4. For each paper, ask as many of the following questions as you have time for:
   1. Did the author state whether and why they did or did not agree with Knuth's definition in premise 1?
      • Note: Knuth's definition is a conjunction of 5 things: premise 1a & premise 1b & premise 1c & premise 1c & premise 1e.

        So, in disagreeing with premise 1, an author must

        1. explicitly disagree with (at least) one of premise 1a … premise 1e.

        2. and say why they disagree with that part (or those parts).
      1. If the author agreed and gave reasons for agreeing, do you agree with those reasons? Why?
      2. If the author disagreed and gave reasons for disagreeing, do you agree with those reasons? Why?

   2. Did the author state whether and why they did or did not agree with the claim about the nature of programming languages in premise 2?
      (Plus question (i) and question (ii), above.)

   3. Did the author state whether and why they did or did not agree with the claim about the "Turing-equivalence" of programming languages in premise 3?
      (Plus question (i) and question (ii), above.)

   4. Did the author state whether and why they did or did not agree with the claim and/or the examples in premise 4?
      (Plus question (i) and question (ii), above.)

   5. Did the author state whether and why they believe that conclusion 5 does or does not validly follow from premise 1&ndashpremise 4?
      Do you agree with their evaluation?

   6. If the author believes that conclusion 5 follows soundly from premise 1–premise 4,
      then they should state that they believe conclusion 5 for that reason.
      Do they?
      1. On the other hand, if the author believes that conclusion 5 does not follow
         —either because one or more of the premises is false or because the argument is invalid—
         then did the author state whether and why they did or did not agree with the statement made in the conclusion?
         (Plus question (i) and question (ii), above.)

      2. Note that if the author believes that the argument is unsound,
         that is not a sufficient reason for disbelieving the claim!
         That's because even a valid argument can have false premises and a true conclusion (or a false one),
         and even an invalid argument can have a true conclusion (or a false one).
         The only thing that can't happen is to have a valid argument with true premises and with a false conclusion.

   7. If the author believes that conclusion 6 follows soundly from statement 5 considered as a premise along with some or all of the previous statements in the argument (and possibly along with one or more missing premises!), then they should state that they believe conclusion 6.
      Do they?

   8. On the other hand, if the author believes that conclusion 6. does not follow
      —either because one or more of its premises is false or because the argument is invalid—
      then did the author state whether and why they did or did not agree with the statement made in the conclusion?
      (Plus question (i) and question (ii), above.)

5. Keep a written record of the questions and replies.
   This will be useful to the author, for revision.

6. At home, over the next week, please revise your paper to take into consideration the comments made by your fellow students (that is, your "peers"): Perhaps defend your claims better, or clarify statements that were misunderstood, etc.
   For help, see your instructor.