CSE/PHI 4/584, Spring 2007

Position Paper #3:

What Is Computation?

Last Update: 5 March 2007

Note: or material is highlighted

For this position paper, I would like you to evaluate the following argument:

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 = f's value 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.
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.
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 procedures depends on the environment in which they are executed.
4. E.g., algorithms can apparently be written that can perform an infinite computation in a finite amount of time (by continually accelerating).
  (And so on.)
Therefore, these programs do not implement Turing machines (contrary to premise 3).
Therefore, they 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.

If it is valid and 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 it 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 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 it because you think the argument is sound; if so, say so. Or you might agree with the conclusion but think that there's something wrong with the argument; if so, then try to present a better argument. Or you might not agree with the conclusion(s); if not, state why, and try to give an argument for what you do believe.

Your position paper should be approximately
Please bring
to lecture on the due date and
to recitation that week.
At the top of the first page, please put the following information in the following format:

Position Paper #3 YOUR NAME

DATE DUE CSE (or PHI) 484 (or 584), Monday (or Wednesday)
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, no abstract is needed for this position paper, but you do need to give full citations to any sources that you cite.

DUE AT THE BEGINNING OF LECTURE, MONDAY, MARCH 19

Position Paper #3		YOUR NAME
DATE DUE		CSE (or PHI) 484 (or 584), Monday (or Wednesday)