------------------------------------------------------------------------
Subject: POSITION PAPER 2 -- ANALYSIS
------------------------------------------------------------------------

This is a long posting, containing a sample analysis of the argument for
Position Paper 2.

There are many ways to analyze any argument, and different analyses
can come up with radically different evaluations.  What follows is
merely *one* way that this argument could have been analyzed.  

The point of this sample is not so much to show you what you *should*
have said (because, after all, what I say below is itself an argument
open to analysis and evaluation). 

Rather, it's main purpose is to show you *how* to analyze an argument.
------------------------------------------------------------------------

Analysis of premise 1:

	Knuth...characterizes the informal, intuitive notion of
	"algorithm" as follows:

	   a. "Finiteness. An algorithm must always terminate after a
              finite number of steps...."

	   b. "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...."

	   c. "Input. An algorithm has zero or more inputs...."

	   d. "Output. An algorithm has one or more outputs...."

	   e. "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...."

------------------------------------------------------------------------
(By the way, his name is "Knuth", pronounced "k'nooth".  It is not
"Kunuth" or "Kunth", as some of you consistently wrote it :-)
http://www-cs-faculty.stanford.edu/~uno/

Also, although this *premise* is his explication of 'algorithm',
the rest of the *argument* is mine, not his.)
------------------------------------------------------------------------

I interpret Knuth's characterization of 'algorithm' to mean that any
algorithm must satisfy this definition. We can simplify a bit as follows:

	premise 1 =
	For any x, x is an algorithm
		   iff
		   x satisfies the definition given above.

For the sake of argument (since it will turn out not to matter!),
let us assume that this is true (it's certainly plausible).

Analysis of premise 2:

	Computer programming languages (like Java, Lisp, Fortran,
	etc.) are formal languages for expressing (or "implementing")
        algorithms.	

I interpret this to mean that any program expressed in a computer
programming language is an algorithm.  (Other interpretations are
possible, as many of you impressed upon me; some of them are even
good interpretations ;-)  So:

	premise 2 = 
	For any x,
	  if   x is a program expressed in a computer programming language,
	  then x is an algorithm.

I will reserve comment on whether this is true or false till our
analysis of premise 4.
(But we can take it to be true; it's pretty reasonable.)

Analysis of premise 3:

	Every computer programming language is equivalent in
	expressibility to a Turing-machine programming language.
   	a. I.e., every program in any programming language can be
	translated into the language for programming Turing machines, and
	vice versa.
   	b. I.e., any function that is computable by any programming language
	is computable by a Turing machine, and vice versa. 

Note, by the way, that this is a *single* premise.  "I.e." is an
abbreviation for the Latin phrase "id est", which means "that is";
in other words, "i.e." means "in other words".

I interpret this to mean that any program is expressible as a TM
program:

	premise 3 = 
	For any x,
	  if   x is a program,
	  then x is expressible as a TM program.

This seems to me to be true.  It is a restatement of the fact that
the class of functions computable by any of the standard models of
computation (TMs, lambda calculus, recursive functions, register
machines, etc.) is the same as the class of functions computable
by any of the others.  Since all high-level, computer-programming
languages, or, to be more precise, any that have sequence, selection,
and (while-)repetition, are TM-equivalent, I take it that premise 3
is true.  As it turns out, it doesn't matter (see below)!

Analysis of premise 4:

	Some real computer programs violate parts of definition 1:
   	a. E.g., airline-reservation systems, ATMs, operating systems,
	etc., never terminate.
   	b. E.g., heuristic AI programs don't always compute exactly the
	function that they were written for, but only come very close.
   	c. E.g., the effectiveness of mundane procedures depends on the
	environment in which they are executed. 
	d. 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.) 

(By the way, as long as I'm teaching you some Latin, "e.g." is an
abbreviation for the Latin phrase "exempli gratia", which means "for the
sake of example", or just "for example", for short.)

I interpret this to mean that there are some programs that are not
algorithms (in the sense of premise 1).  The easiest way to think about
this is to consider one such program (it doesn't matter which).
Call it "p".  Then premise 4 is:

	p (whatever it is) is a program that is not an algorithm.

Now, note that my interpretation of premise 4 is the *negation* of
my interpretation of premise 2!  (Premise 2 says that EVERY program is
an algorithm; premise 4 says that SOME program is NOT an algorithm.)

That means that both of them can't be true at the same time,
which means that it's impossible for all of the premises to be true
simultaneously!

I.e., we have an example of an argument with inconsistent premises.
That means that it is valid, NO MATTER WHAT ITS CONCLUSION IS!

(It's a principle of logic that, from a false statement, anything
whatsoever follows.  The conjunction of our premises must be false,
because two of them are negations of each other, so anything follows,
including conclusion 5.)

Let me repeat:  This IS a valid argument
(as I have interpreted it; remember, other interpretations are possible).

	[In case you're still not convinced, consider this:
	To show that p is not expressible as a Turing-machine program,
	we would need to show that p is not a computer program.
	To do that, we would need to show that p is not an algorithm.
	But that's easy to show, since we already have that p is not an
        algorithm by the way we defined p.  I.e., because p is not an
	algorithm, we can conclude that p is not a program, from which
        we can infer that p is not expressible as a TM program.]

Because premises 2 and 4 are inconsistent, we can *make* the argument
consistent by *rejecting* one of them.  Let's consider both possibilities:

Case 1:  Reject 2; keep 4:  Then our premises become:

	1. for any x,
		x is an algorithm
		iff
	   	x satisfies Knuth's definition

	3. for any x,
		if   x is a program,
           	then x is expressible as a TM program

	4. p is a program but not an algorithm

Can we show 5?  What does 5 say?

	These programs do not implement TMs.

"These programs" refers to programs like p.  So, 5 says:

	p is not expressible as a TM program

Now, if we can show that p *is* a computer program, then premise 3 will
allow us to conclude that p *is* expressible as a TM program.
And, indeed, we have that p is a computer program.  
So, we have that p is expressible as a TM program.  
So, we *cannot* show that p is NOT expressible as a TM program!  

So, in this case, the revised argument is invalid,
and the correct conclusion is that p IS expressible as a TM program,
i.e., that all the examples in premise 4 are indeed Turing-computable.

Case 2:  Reject 4; keep 2: Then our premises become:

	1. for any x,
		x is an algorithm
	   	iff
		x satisfies Knuth's definition

	2. for any x,
		if   x is a computer program,
	   	then x is an algorithm

	3. for any x,
		if   x is a computer program,
	   	then x is expressible as a TM program
	
NOW can we show 5, i.e., that p is *not* expressible as a TM program,
where p is both a computer program but not an algorithm?

But there is no such p, because, by premise 2, if p is a computer
program, then it *is* an algorithm.  So, in this case, too, the revised
argument is invalid, but this time the correct conclusion is that
x *is* expressible as a TM program.

What about conclusion 6?  For 6 to follow from 5, we need to show
that if p is not expressible as a TM program, then p is not computable.
Taking the contrapositive, this means we have to show that if p is
computable, then it is expressible as a TM program.

Given premise 3, which says that, if p is a *computer* program,
then it is expressible as a *TM* program,
we might try to show that, if p is computable, then p is a computer program.  
To do that, we would need a definition of "computable"
(as many of you noted),
but the argument doesn't provide that, so 6 does NOT follow from 5.

To summarize:

We see that 5 validly--but trivially--follows from 1-4,
but since 1-4 are inconsistent, the argument from 1-4 to 5 is unsound.  

And we see that the argument from 5 to 6 is invalid.

However, we *still* need to decide if we think that 5 and 6 are
true, independently of this particular argument.  After all, you
might be able to think of a better argument for 5 or for 6.  I won't
provide that here, however, since we need to move on to other issues.