Position Paper #2:

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:
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).
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" 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/2ⁿ 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.

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

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

if so, say so.

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

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.
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)
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

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