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

1. Notation:
   "=df" means: "means by definition"
   "≈df" means: "roughly means by definition"

   ---

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.

   Strictly speaking, this is not correct, because functions (considered extensionally) don't "do" anything.

   However, a computer can be viewed as such a machine!

   ---

4. Sometimes functions are described ("intensionally" and non-uniquely) by formulas.
   (See Wangsness & Franklin 1966, Huber 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
   • Note: Formulas are not algorithms.
     
     For an interesting discussion of the distinction, see:
     Chater, Nick; & Oaksford, Mike (2013),
     "Programs as Causal Models: Speculations on Mental Programs and Mental Representation",
     Cognitive Science 37(6) (August): 1171–1191, esp. p. 1172.
     

   ---

5. A function f is computable ≈df there is an "algorithm" that computes f;

   i.e., there is an algorithm A_f such that, for all input i, A_f(i) = f(i)

   • i.e., A_f and f have the same input-output "behavior"

         and A_f specifies how f's input and output are related…

   • i.e., A_f is a procedure, or a mechanism, or a set of intermediate steps
   • i.e., it's not arbitrary or magic

6. …where an algorithm for a problem P

   (the word "algorithm" comes from the name "Al-Khuwarizmi", Arab mathematician, ca. 780-850 AD, i.e., about 1200 years ago)

   ≈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. the number of steps actually used to compute the solution must be finite,

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

   4. and it must output a correct solution to P.
      • (Must it? What about heuristics?)
   Examples of algorithms:
   1. A_f (i) =
      input i;
      add 1 to i;
      output result.

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

   3. A_f′ (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. Four Great Insights of Computer Science:
   • The first three "great insights" help make precise the vague notions above.
     The fourth insight links the vague notion with a precise one.
     Together, they define the smallest possible language in which you can write any procedure for any computer.
   1. Bacon's, 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 details on how to compute with real numbers, see:
        Braverman, Mark (2013),
        "Computing with Real Numbers, from Archimedes to Turing and Beyond",
        Communications of the ACM 56(9) (September): 74–83.
        

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

      • For a literary and philosophical view of this, see:
        • Quine, Willard van Orman (1987), Quiddities: An Intermittently Philosophical Dictionary
          (Cambridge, MA: Harvard University Press), "Universal Library", pp. 223-225;
          very short and definitely worth reading!

      • 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; see Weizenbaum 1976),
      • 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).)

        For more info on this particular model of Turing machines, see:
        

      • Schagrin, Morton L.; Rapaport, William J.; & Dipert, Randall D. (1985), Logic: A Computer Approach (New York: McGraw-Hill), Appendix B ("Turing Machines"): 327-339 [PDF].
      • For more info on other models of Turing machines, see the "Turing machine" link above.

   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

      …where—recursively—"this" and "that" can be:

      • any of the basic instructions, or
      • any complex instruction created by application of any grammatical rule.

      The optional additional grammatical rules are:

      1. exit:
         (for simplicity or elegance)

      2. named procedures (or: procedural abstraction):
         • Define new (typically, complex) actions by name
         • (even more optional, but conceptually 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 is_df (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

        • (But see the literature on "hypercomputation".)

      • 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–2013 by William J. Rapaport (rapaport@buffalo.edu)
   http://www.cse.buffalo.edu/~rapaport/computation.html-20130920