WHAT IS COMPUTATION?

William J. Rapaport

Department of Computer Science and Engineering,
Department of Philosophy,
and Center for Cognitive Science
State University of New York at Buffalo,
Buffalo, NY 14260-2000

0.  Notation:  `=df' means:  "means by definition"
               `~df' means:  "roughly means by definition"

1.  A _function_ is a set of input-output pairs.

2.  A function f _is computable_ =df there is an *algorithm* that computes f;
                                   i.e., there is an algorithm A such that
                                         for all input i, A(i) = f(i),

    where an _algorithm_ (from "Al-Khuwarizmi", Arab mathematician,
    ca. 780-850 AD) ~df a *procedure* for solving a problem such that:

                        (a) it 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 executor

                   and  (b) it is *effective*; i.e., it must eventually
                            *halt* and it must be *correct*

3.  3 Great Insights of Computer Science:

    (a)  There are only 2 objects a computer has to deal with in order
         to *represent* "anything"

    (b)  There are only 5 actions a computer has to perform in order to
         *do* "anything"

    (c)  Only 3 ways of combining these actions are needed for a
         computer to do "anything" 

About (a):  Boole, Shannon: Can use 0, 1 to represent any discrete thing
            	  	    (and can approximate continuous things)

About (b):  Turing:  Every algorithm can be expressed in a language for
                     a computer (a "Turing Machine") consisting of a tape
                     with a linear array of discrete locations and with
                     read/write heads, whose only nouns (names for objects)
                     are `0', `1' and whose only verbs (basic actions) are:
                            Move-left(-1-location)
                            Move-right(-1-location)
                            Print-0(-on-the-current-location)
                            Print-1(-on-the-current-location)
                            Erase(-the-current-location)

About (c):  Boehm & Jacopini:
                     Only need the following to create complex actions:

                     - sequence (do this; then do this)
                     - selection (IF this is the case,
                                     THEN do that
                                     ELSE do other thing)
                     - loop (WHILE this is the case, DO the following)
            + a halt command
            + ability to define new complex actions by name
              (i.e.,  procedures, or subroutines)

4.  The Church-Turing Thesis:

	Effective computability =df TM computability
        
    I.e., an algorithm is   (expressible as) a TM program.
                         df

    This is a *proposed* definition.

    How do we know that TM computability captures the intuitive notion
    of effective computability?

    Evidence:

    - Turing's analysis of computation (NB:  <> the Turing Test for AI!!)
    - The following formalisms are all constructively equivalent
      (i.e., inter-compilable):
               * Turing Machines
               * Post Machines (use tape as a queue)
               * lambda calculus (Church; cf. Lisp)
               * Markov algorithms (cf. Snobol)
               * Post productions (cf. production systems)
               * Herbrand-Goedel recursion equations (cf. Algol)
               * mu-recursive functions
               * register machines
    - Empirical evidence:  All algorithms so far translate to TMs
      i.e., there are no intuitively effective computable algorithms
            that are not TM computable

5.  Are there functions that are non-computable?  Yes!  For more info,
see: