CSE 4/510 & PHI 498, Spring 2004
Position Paper #2: What Is Computation?
Last Update: 17 February 2004
material is highlighted
For this position paper, I would like you to evaluate the
- An algorithm, A, for solving a problem P (or, for computing
a function F) is a
finite procedure (i.e., a finite set of instructions) for solving P (or, computing F) that is:
- unambiguous for the computer or human who will execute it;
i.e., all steps of the procedure must be clear and well-defined for the
i.e., A must eventually halt,
and it must output a correct solution to P (or, the correct
computation of F).
- Computer programming languages (like Java, Lisp, Fortran, etc.) are
formal languages for computing 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 problem that is solvable by any programming language
(or, any function that is computable by any programming language)
is solvable (or, 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 solve exactly
the problem 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. (And so on.)
- Therefore, these programs cannot be modeled by 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 determine whether it is "factual"
and whether it is valid.
- If it is both, then it is said to be 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 it is "unfactual" [i.e., one or more of the
premises are false] or it is invalid [i.e., there is some way for the premises to
be true yet for the conclusion to be false].
To determine whether it is "factual", you must decide whether each
premise is true or false (more realistically, you must decide whether
you believe, or agree with, each premise), and you must explain
why or why not.
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)?
Finally, do you agree with the conclusion(s)? If you do, but you think
that there's something wrong with the argument, try to present a
better one. If you don't agree with the conclusion(s), state why,
and try to give an argument for what you do believe.
Your position paper should be approximately
|1-2 typed pages, double-spaced (i.e., about 250-500 words),
to class on the due date.
This paper only needs the title "Position Paper #2", your name, the
date, and the course number (410, 498, or 510) at the top of the page.
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".
DUE AT THE BEGINNING OF LECTURE, TUESDAY, FEBRUARY 24
Copyright © 2004 by
William J. Rapaport