Philosophy of Computer Science

Position Paper #2:

What Is Computation?

Last Update: 24 February 2010

Note: NEW or UPDATED material is highlighted

For this position paper, please evaluate the following argument:

  1. Knuth 1973: 4–6 characterizes the informal, intuitive notion of "algorithm" as follows:

    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; i.e., 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. I.e., every program in any programming language can be translated into the language for programming Turing machines, and vice versa.

    2. I.e., 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 definition 1:

    1. E.g., airline-reservation systems, ATMs, operating systems, etc., never terminate.

    2. E.g., heuristic AI programs don't always compute exactly the function that they were written for, but only come very close.

    3. E.g., the "effectiveness" of "mundane" or everyday procedures (like recipes) depends on the environment in which they are executed.
      • E.g., 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. E.g., algorithms can apparently be written that can perform an infinite computation in a finite amount of time (by continually accelerating).
      • E.g., we can sum the terms of an infinite sequence in a finite amount of time if we take 1/2n second to add the nth term.

    • And so on.

  5. Therefore, these programs UPDATED [i.e., the "real programs" referred to in premise 4] do not implement Turing machines (contrary to premise 3).

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

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.

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: lines 5 and 6.

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

Finally, do you agree with the conclusion(s)?

  1. Your position paper should be approximately

  2. Please bring to lecture on the due date.

  3. At the top of the first page, please put the following information in the following format:

    Position Paper #2, 1st draft                 YOUR NAME
    DATE DUE                 CSE 484 (or CSE or PHI 584)

  4. For general assistance with writing (including my preferred 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.


Copyright © 2010 by William J. Rapaport (