Philosophy of Computer Science

# What Is Computation?

 Last Update: 24 February 2010 Note: or material is highlighted

For this position paper, please evaluate the following argument:

 Knuth 1973: 4–6 characterizes the informal, intuitive notion of "algorithm" as follows: "Finiteness. An algorithm must always terminate after a finite number of steps…" "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…" "Input. An algorithm has zero or more inputs…" "Output. An algorithm has one or more outputs…" "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 aboveand that, for any input i, A's output for i = f's output for i; i.e., for any i, A(i) = f(i). Computer programming languages (like Java, Lisp, Fortran, etc.) are formal languages for expressing (or "implementing") algorithms. Every computer programming language is equivalent in expressibility to a Turing-machine programming language. I.e., every program in any programming language can be translated into the language for programming Turing machines, and vice versa. I.e., any function that is computable by any programming language is computable by a Turing machine, and vice versa. Some real computer programs violate parts of definition 1: E.g., airline-reservation systems, ATMs, operating systems, etc., never terminate. E.g., heuristic AI programs don't always compute exactly the function that they were written for, but only come very close. 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"? 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. Therefore, these programs [i.e., the "real programs" referred to in premise 4] do not implement Turing machines (contrary to premise 3). Therefore, they [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.

• 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
[i.e., 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: lines 5 and 6.

So, do you agree that conclusion 5 follows logically from premises 1–4 and/or that conclusion 6 follows logically from 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)?

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

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.

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

 5 copies
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.

 DUE AT THE BEGINNING OF LECTURE, MONDAY, FEBRUARY 22