CSE 4/510 & PHI 498, Spring 2004

Position Paper #2: What Is Computation?

Last Update: 17 February 2004

Note: NEW or UPDATED material is highlighted

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

  1. 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:

    1. 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 executor

      and

    2. effective; i.e., A must eventually halt, and it must output a correct solution to P (or, the correct computation of F).

  2. Computer programming languages (like Java, Lisp, Fortran, etc.) are formal languages for computing algorithms.

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

  4. Some real computer programs violate parts of definition 1:

    1. E.g., airline-reservation systems, ATMs, operating systems, etc., never halt.

    2. E.g., heuristic AI programs don't always solve exactly the problem 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. (And so on.)

  5. Therefore, these programs cannot be modeled by Turing machines (contrary to premise 3).

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

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

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.