Philosophy essay

!  What is a computer? !  Can computers have intelligence? !  Are human beings computers? !  If so, is that what makes us intelligent, or constitutes

our having minds?

Babbage’s Analytical Engine

Ada Lovelace (1815 – 1852)

Functions and Algorithms

!  A function is a mapping from numbers (or ordered sets of numbers) to numbers (or ordered sets of numbers). !  Examples : addition and multiplication are functions mapping

pairs of numbers to single numbers.

!  An algorithm is an effective procedure for calculating the value of a function. An effective procedure is defined as follows:

1.  At each stage of the procedure, there is a definite thing to do next. Moving from step to step does not require any special guesswork, insight or inspiration.

2.  The procedure can be specified in a finite number of steps.

A algorithm for multiplying two numbers, X and Y 62 COMPUTATION AND REPRESENTATION

Write 0 on the ANSWER Does the number written on X = 0?

If no, go to step (iii)

Subtract 1 from the number written on X and go to step (iv)

If yes, go to step (v)Stop

Add the number written on Y to the ANSWER and go to step (ii)

)ii()i(

(iii)

(iv)

(v)

Figure 2 Flow chart for the multiplication algorithm.

Figure 2 shows the flow chart; it represents the calculation by the following series of steps:

Step (i): Write ‘0’ on the ANSWER, and go to step (ii). Step (ii): Does the number written on X = 0? If YES, then go to step (v) If NO, then go to step (iii) Step (iii): Subtract 1 from the number written on X, write the result on X, and go to step (iv) Step (iv): Add the number written on Y to the ANSWER, and go to step (ii) Step (v): STOP

Let’s apply this to a particular calculation, say 4 times 5. (If you are familiar with this sort of procedure, you can skip this example and move on to the next paragraph.)

Begin by writing the numbers to be multiplied, 4 and 5, on the X and Y pieces of paper respectively. Apply step (i) and write 0 on the ANSWER. Then apply step (ii) and ask whether the number written on X is 0. It isn’t – it’s 4. So move to step (iii), and subtract 1 from the number written on X. This leaves you with 3, so you should write this down on X, and move to step (iv). Add the number written on Y (i.e. 5) to the ANSWER, which makes the ANSWER read 5. Move to step (ii), and ask again whether the number on X is 0. It isn’t – it’s 3. So move to step (iii), subtract 1 from the number written on X, write down 2 on X and move to step (iv). Add the number written on Y to the ANSWER, which makes the ANSWER read 10. Ask again whether the number written on X is 0. It isn’t – it’s 2. So move to step (iii), subtract 1 from the number written on X, write down 1 on X and move to step (iv). Add the number written on Y to the ANSWER, which makes the ANSWER read 15. Ask again whether the number written on X is 0; it isn’t, it’s 1. So move to step (iii), subtract 1 from the number written on X, write down 0 on X and move to step (iv). Add the number written on Y to the ANSWER, which makes the ANSWER read 20. Move to step (ii) and ask whether the number written on X is 0. This time it is, so move to step (v), and stop the procedure. The number written on the ANSWER is 20, which is the result of multiplying 4 by 5.1

This is a pretty laborious way of multiplying 4 by 5. But the point of the illustration is not that this is a good procedure for us to use. The point is rather that it is an entirely effective procedure:

An algorithm for boiling an egg

COMPUTATION AND REPRESENTATION 63

at each stage, it is completely clear what to do next, and the procedure terminates in a finite number of steps. The number of steps could be very large; but for any pair of finite numbers, this will still be a finite number of steps.

Steps (iii) and (iv) of the example illustrate an important feature of algorithms. In applying this algorithm for multiplication, we employ other arithmetical operations: subtraction in step (iii), addition in step (iv). There is nothing wrong with doing this, so long as there are algorithms for the operations of subtraction and addition too – which of course there are. In fact, most algorithms will use other algorithms at some stage. Think of long multiplication: it uses addition to add up the results of the ‘short’ multiplications. Therefore, you will use some algorithm for addition when doing long multiplication. So our laborious multiplication algorithm can be broken down into steps which depend only on other (perhaps simpler) algorithms and simple ‘movements’ from step to step. This idea is very important in understanding computers, as we shall see.

The fact that algorithms can be represented by flow charts indicates the generality of the concept of an algorithm. As we can write flow charts for all sorts of procedures, so we can write algorithms for all sorts of things. Certain recipes, for example, can be represented as flow charts. Consider this algorithm for boiling an egg.

1 Turn on the stove. 5 When the timer rings, turn off the gas. 2 Fill the pan with water. 6 Remove the egg from the water. 3 Place the pan on the stove. 7 Result: one boiled egg. 4 When the water boils, add one egg, and

set the timer.

This is a process that can be completed in a finite number of steps, and at each step there is a definite, unambiguous, thing to do next. No inspiration or guesswork is required. So, in a sense, boiling an egg can be described as an algorithmic procedure (see Figure 3).

Turn on the stove

Fill the pan with water

Place the pan on the stove

Is the water boiling?

If yes, then add one egg

Set the timer

When the timer rings, turn

off the gas

If no, then wait

Result: one boiled egg!

Remove the egg from the water

Figure 3 A flow chart for boiling an egg.

Turing Machines A Turing machine (abstract version) is a machine with:

!  Possible Internal States : We can label them S1, S2, …….Sk

!  Possible Inputs : We can label them I1, I2, …….Ij !  Possible Outputs : We can label them O1, O2, …..Om

!  Machine table (algorithm): A set of instructions the machine follows, of the form : If you are in state S20 and receive input I34, then go into state S51 and output O283.

An example of an Abstract Turing Machine !  Coke Machine:

Turing Machines !  Turing described a more specific machine that is a simple,

precise way of realizing the abstract idea of a computation machine we just described. It has:

1.  An infinite tapehead with a series of 1’s and 0’s 2.  A control unit, in a certain internal state than can be

changed 3.  5 basic operations: move left, move right, read, write,

change internal state 4.  A algorithm given by a machine table

Universal Turing Machines

!  An important insight : The Turing machine algorithm itself can be encoded as a binary sequence.

!  For this, we just need binary codes for the internal states and operations of the machine (read, write, move etc).

!  So we can make a programmable computer that can run any Turing machine algorithm!

The scope of Turing machine algorithms

!  Church/Turing thesis : Any algorithmic procedure can be carried out by a Turing machine.

!  That is, any numerical function that can be computed, can be computed by a Turing machine.

!  A consequence: any algorithmic procedure that can be encoded in terms of mappings from numbers to numbers can be computed by a Turing machine (i.e. even something like an algorithm for boiling an egg!).

!  Turing wasn’t trying to describe a machine that would work well in real life – he was making abstract theoretical points about the nature of computation.

!  Modern computers are abstractly just turing machines, but designed to deal with real world constraints on computing, such as memory size and computing time.

Good old fashioned AI

!  Sometimes known as classical or symbolic AI, this is computing using rules and representations.

!  What the computer “knows” is a stored as a set of sentences, in binary code (it’s data). It can follow rules in the form of algorithms, which can also be stored. It can process information by transforming data and input representations (e.g. from a camera or keyboard), into output representations (e.g. a transformation of its data, or an output on a screen).

Example: Missionaries and Cannibals problem solver

designed their program to mimic what they believed were the students’ thought processes.

I won’t go into the details of how GPS worked, but its symbolic nature can be seen by the way the program’s instructions were encoded. To set up the problem, a human would write code for GPS that looked something like this:

CURRENT STATE: LEFT-BANK = [3 MISSIONARIES, 3 CANNIBALS, 1 BOAT] RIGHT-BANK = [EMPTY]

DESIRED STATE: LEFT-BANK = [EMPTY] RIGHT-BANK = [3 MISSIONARIES, 3 CANNIBALS, 1 BOAT]

In English, these lines represent the fact that initially the left bank of the river “contains” three missionaries, three cannibals, and one boat, whereas the right bank doesn’t contain any of these. The desired state represents the goal of the program—get everyone to the right bank of the river.

At each step in its procedure, GPS attempts to change its current state to make it more similar to the desired state. In its code, the program has “operators” (in the form of subprograms) that can transform the current state into a new state and “rules” that encode the constraints of the task. For example, there is an operator that moves some number of missionaries and cannibals from one side of the river to the other:

MOVE (#MISSIONARIES, #CANNIBALS, FROM-SIDE, TO-SIDE)

The words inside the parentheses are called arguments, and when the program runs, it replaces these words with numbers or other words. That is, #MISSIONARIES is replaced with the number of missionaries to move, #CANNIBALS with the number of cannibals to move, and FROM-SIDE and TO-SIDE are replaced with “LEFT-BANK” or “RIGHT-BANK,” depending on which riverbank the missionaries and cannibals are to be moved from. Encoded into the program is the knowledge that the boat is moved along with the missionaries and cannibals.

designed their program to mimic what they believed were the students’ thought processes.

I won’t go into the details of how GPS worked, but its symbolic nature can be seen by the way the program’s instructions were encoded. To set up the problem, a human would write code for GPS that looked something like this:

CURRENT STATE: LEFT-BANK = [3 MISSIONARIES, 3 CANNIBALS, 1 BOAT] RIGHT-BANK = [EMPTY]

DESIRED STATE: LEFT-BANK = [EMPTY] RIGHT-BANK = [3 MISSIONARIES, 3 CANNIBALS, 1 BOAT]

In English, these lines represent the fact that initially the left bank of the river “contains” three missionaries, three cannibals, and one boat, whereas the right bank doesn’t contain any of these. The desired state represents the goal of the program—get everyone to the right bank of the river.

At each step in its procedure, GPS attempts to change its current state to make it more similar to the desired state. In its code, the program has “operators” (in the form of subprograms) that can transform the current state into a new state and “rules” that encode the constraints of the task. For example, there is an operator that moves some number of missionaries and cannibals from one side of the river to the other:

MOVE (#MISSIONARIES, #CANNIBALS, FROM-SIDE, TO-SIDE)

The words inside the parentheses are called arguments, and when the program runs, it replaces these words with numbers or other words. That is, #MISSIONARIES is replaced with the number of missionaries to move, #CANNIBALS with the number of cannibals to move, and FROM-SIDE and TO-SIDE are replaced with “LEFT-BANK” or “RIGHT-BANK,” depending on which riverbank the missionaries and cannibals are to be moved from. Encoded into the program is the knowledge that the boat is moved along with the missionaries and cannibals.

Is the human mind a classical computer?

!  Data: Our beliefs and other information encoded in brain.

!  Internal states : our mental states (desires, emotions etc) !  Inputs : from sense organs !  Outputs : changes to mental states, behavior. !  Algorithm : instructions for how rationally update

mental states and act in the world, given perception.

!  In short, the mind consists of representations, and computations (rational inferences), that update the representations and control behavior.

! Time flies like an arrow!

The Language of Thought

!  A strong version of the classical computational view says that not only does the mind use representations and computations, but furthermore the mental representations have a linguistic format. The human mind has “language of thought” that it uses to represent the world.

!  Alternatives: (1) mental representations have an imagistic format, or are unstructured (2) The mind does not use representations at all.

Searle’s critique of Classical AI

!  Strong AI : For any given mental capacity, there is a digital computer program such that running that program is sufficient for having that capacity.

!  Weak AI : A correctly programmed computer is helpful tool in studying the mind, because it enables us to simulate mental processes. But having a mental capacity need not be the same thing as running a certain program.

!  Searle’s argument against Strong AI : Computers do not need to understand the symbols they are manipulating to run a program. The symbols need not even have any meaning!!

Syntax vs Semantics !  A symbol, such an English word, and English

sentence, or a symbol written in a computer’s memory, can have both syntactic and semantic properties.

!  Syntax – The completely formal properties of a symbol, such as the physical shape of letters and words.

!  Semantics – The facts about what the symbol means, or what it is used to represent in the world, or represent about the world.

!  Digital computers only operate on syntax: In a turing machine, information is encoded in a series of 1s and 0s. The machine is not sensitive to what is encoded by the 1s and 0s, or what they mean, only their syntactic shape.

1.  Running a certain computer program only requires that the computer has internal states with the right syntax, being processed according to a certain algorithm.

2.  “Syntax is not sufficient for semantics” 3.  Therefore, running a computer program is not

sufficient for semantics.

What gives symbols meaning?

!  Three important ideas:

!  (1) Mental symbols get their meaning because of their connection to the external items in the environment that they carry information about.

!  (2) Mental symbols get their meaning because of the functional role they play in the mental economy of the system.

!  (3) In the case of computer symbols, or human language, symbols have meaning because we intentionally give them a certain interpretation.

!  If (1), then we still can have a view in the spirit strong AI. Having a mind involves and internal and external component:

!  Internal component : being a digital computer of a certain kind

!  External component : being hooked up to the environment in such a way that your mental symbols carry useful information (or have meaning in the relevant sense).

!  For option (2), consider three examples of an “internal functional role view”:

!  Associational semantics: Words/symbols get their meaning from “the company that they keep” – that is, from the other words that we readily associate with them.

!  Definitional Semantics : Words/symbols get their meaning from the definitions of them that we can give in terms of other words.

!  Conceptual role semantics : Words/symbols get their meaning from the inferences we can make from them. !  E.g. I can infer “Fido is an animal” from “Fido is a dog”.

!  With all these “internal role” theories of meaning, there’s no reason why running the correct algorithm on the sentences couldn’t give them the right functional roles. So on these views, syntax (understood as including the internal functional role of symbols) can be sufficient for semantics.