CSE/PHI 4/584, Spring 2007
Position Paper #3:
What Is Computation?
Last Update: 5 March 2007
material is highlighted
For this position paper, I would like you to evaluate the
- 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 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.
- I.e., every program in any programming language can be translated
into the language for programming Turing machines, and vice versa.
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.,
- 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 procedures depends on
the environment in which they are executed.
- 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!
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
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
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,
and try to give an argument for what you do believe.
Your position paper should be approximately
to lecture on the due date and
recitation that week.
At the top of the first page, please put the following information in
the following format:
|Position Paper #3
||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
Copyright © 2007 by
William J. Rapaport