Philosophy of Computer Science

# 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, NY14260-2000

 Last Update: 20 September 2013 Note: or material is highlighted

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

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)

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

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

• i.e., Af 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.

Examples of algorithms:

1. Af (i) =
input 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;
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:

• 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),
• 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).)

• 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].

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