The Wayback Machine - https://web.archive.org/web/20010214002845/http://www.cse.buffalo.edu:80/~rapaport/computation.html

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


Copyright © 2000 by William J. Rapaport ([email protected])
file: computation.24ag00.html