What Is Computation?

William J. Rapaport

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

Last Update: 18 March 2007

Note: NEW or UPDATED material is highlighted

  1. Notation:

  2. A function (described "extensionally") is a set of input-output pairs
    (such that no two of them have the same first element).

      Examples of functions:

    1. f = {<0,1>, <1,2>, <2,3>,...}

      • sometimes written f(0)=1, f(1)=2,...

    2. g = {<0,0>, <1,2>, <2,4>, <3,6>,...}

      • sometimes written g(0)=0, g(1)=2,...

    3. A finite function:

      h = {<"yes", print "hello">, <"no", print "bye">, <input ≠ "yes" & input ≠ "no", print "sorry">}

      • this function prints "hello", if the input is "yes";
        it prints "bye", if the input is "no";
        and it prints "sorry", if the input is neither "yes" nor "no"

    4. A partial function:

      k = {<0,1>, <2,4>, <4,8>,...}

      • i.e., k(1), k(3),... are undefined.

  3. Sometimes functions are characterized as "machines" that take input into a "black box" with a "crank" that mysteriously converts the input into output. Note that a computer can be viewed as such a machine!

  4. Sometimes functions are described ("intensionally" and non-uniquely) by formulas.
    (See Wangsness & Franklin 1966, Humber 1966, Knuth 1966.)

      Examples of formulas:

    1. f(i) = i+1

      • Or f'(i) = 2i-i+7÷(3+4) = f(i)

    2. g(i) = 2i

  5. A function f is computable ≈df there is an "algorithm" that computes f;
    i.e., there is an algorithm Af such that for all input i, Af(i) = f(i)
          and Af specifies how f's input and output are related...

  6. ...where an algorithm for a problem P ≈df a finite procedure (i.e., a finite set of instructions) for solving P that is:

    1. "effective" or unambiguous for the computer or human who will execute it;

      • Note that "effective" and "unambiguous" are vague terms, and the relativity to a specific computer or human makes it even vaguer.

      • i.e., all steps of the procedure must be clear and well-defined for the executor;
          (but note that "clear" and "well-defined" are equally vague!)

      • i.e., the executor must always be able to determine (i.e., to know) how to execute each step and what to do next

        • this is also pretty vague, but it does rule out certain recipes

        and must be able to execute each step (in a finite amount of time?)

        • So: We need to have more precise notions of what to do and when to do it.

    2. it must eventually halt,

      • (Must it? What about programs like Google, or a program to compute all primes or print all integers?)

    3. and it must output a correct solution to P.

      Examples of algorithms:

    1. Af (i) =
        input i;
        add 1 to i;
        output result.

    2. Ag (i) =
        input i;
        multiply i by 2;
        output result.

    3. Af' (i) =
        input i;
        multiply i by 2;
        subtract i from previous value;
        add 7 to previous value;
        add 3 to 4;
        divide previous value by result;
        output final result.

  7. Great Insights of Computer Science:

    1. Leibniz's, Boole's, Turing's, Shannon's, & Morse's Insight.

        All the information about any computable problem can be represented using only 2 nouns: 0, 1 (or any other bistable pair that can flip-flop between two easily distinguishable states, such as "on"/"off", "magnetized/de-magnetized", "high-voltage/low-voltage", etc.).

        • Strictly speaking, these can be used to represent discrete things; continuous things can be approximated to any desired degree, however.

        • For more information, see "Great Ideas in Computer Science": Lecture Notes #2, Lecture Notes #3.

        • For a literary and philosophical view of this, see:

        • This limitation to 2 nouns is not required: Turing's original theory had no restriction on how many symbols there were. There were only restrictions on the nature of the symbols (they couldn't be too "close" to each other; i.e., they had to be distinguishable) and that there be only finitely many.

    2. Turing's Insight.

        Every algorithm can be expressed in a language for a computer (viz., a Turing machine) consisting of an arbitrarily long paper tape divided into squares (like a roll of toilet paper, except you never run out), with a read/write head, whose only nouns are "0" and "1", and whose only 5 verbs (or basic instructions) are:

        1. move-left-1-square
        2. move-right-1-square

          • (These could be combined into a single verb (i.e., a function) that takes a direct object (i.e., a single argument): move(location).)

        3. print-0-at-current-square
        4. print-1-at-current-square
        5. erase-current-square

          • (These could be combined into another single, transitive verb: print(symbol), where symbol could be either "0", "1", or "blank" (here, erasing would be modeled by printing a blank).)

    3. Boehm and Jacopini's Insight: Structured Programming

        Only 3 grammar rules (or maybe a few more, for elegance or clarity) are needed to combine any set of basic instructions into more complex ones:

        1. sequence:

            first do this; then do that

        2. selection (or choice):

            IF such-&-such is the case,
            THEN do this
            ELSE do that

        3. repetition (or looping):

            WHILE such & such is the case
            DO this

        The optional additional grammatical rules are:

        1. exit:

            (for simplicity or elegance)

        2. named procedures NEW (or: procedural abstraction):

          • Define new complex actions by name
          • (even more optional, but very powerful)

        3. recursion:

            (elegant replacement for repetition)

        (For more info, see "Great Ideas in Computer Science": Lecture Notes #3, Lecture Notes #4 .

    4. The (Church-)Turing Thesis.

      Effective computability =df (anything equivalent to) Turing-machine computability

      I.e., an algorithm isdf (expressible as) (anything equivalent to) a Turing-machine program.

      This is a proposed definition. How do we know that Turing-machine 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-Gödel recursion equations (cf. Algol)
        • µ-recursive functions
        • register machines

      • Empirical evidence: All algorithms so far translate to Turing-machines

        i.e., there are no intuitively effective computable algorithms that are not Turing-machine computable

      • For more details, see "Structured Programming and Recursive Functions" [PDF]

      • Are there functions that are non-computable? Yes! For more info, see: "The Halting Problem"

    Copyright © 1992-2007 by William J. Rapaport (rapaport@cse.buffalo.edu)
    file: computation-20070318.html