Thinking and Computation
Chapter1:ThinkingandComputation ⃝c Levesque2011 1
Intelligent behaviour
Copyright By PowCoder代写 加微信 powcoder
In this course, we will consider what it takes to get a computer to engage in intelligent activities such as
• understanding English sentences;
• recognizing objects in a visual scene; • planning courses of actions;
• solving recreational puzzles;
• playing strategic games.
What these very different activities all have in common, is that when they are performed by people, they appear to require thought.
Chapter1:ThinkingandComputation ⃝c Levesque2011 2
Are computers electronic brains?
Historically, models of the brain have often been associated with the most advanced technology of the time.
• clockwork
• steam engine
• telephone switchboard
• and now it’s . . . computers!
Invariably, we end up laughing at these simplistic models!
• found to be simplistic, misleading
• tell us very little about what we are, and how we do what we do
Why should we think computers are any different??
Chapter1:ThinkingandComputation ⃝c Levesque2011 3
In this course, as in much of AI, we will be concerned with thinking (of various sorts), but have very little to say about the brain.
Here is a useful analogy: the study of flight (before airplanes)
• we might like to understand how animals like birds can fly • we might want to build machines that are capable of flight
Two possible strategies:
1. study birds, their feathers, muscles, very carefully and construct machines to emulate them
2. study aerodynamics: principles of flight applicable to anything We will be following the second strategy here (for thinking, not flight).
Chapter1:ThinkingandComputation ⃝c Levesque2011 4
Q: What is thinking?
A: Thinking is a process that occurs in the brain over time, but largely unconsciously.
Let’s look at thinking in action. . . Read this sentence:
The trophy would not fit into the brown suitcase because it was too small.
Now answer this question:
What was too small? What is the “it ”?
How did you figure this out?
Chapter1:ThinkingandComputation ⃝c Levesque2011 5
Using what you know
Observe: There is nothing in the sentence itself that gives away the answer!
To see this, replace “small” by “big”:
The trophy would not fit into the brown suitcase because
it was too big. Now what is the “it ”?
So you have to use a lot of what you knew about the sizes of things, things fitting inside of other things etc. even if you are unaware of it.
This is thinking!
Roughly: Bringing what you know to bear on what you are doing.
Chapter1:ThinkingandComputation ⃝c Levesque2011 6
What sort of process is thinking?
It is a biological process that happens in the brain.
Like digestion in the stomach? Like mitosis in cells?
Key Conjecture: thinking can be usefully understood as a computational process
Perhaps thinking has more in common with multiplication or sorting a list of names, than with digestion or mitosis.
This is extremely controversial!
We will spend most of the course exploring this one idea.
But first we need to understand what “computational process” means . . .
Chapter1:ThinkingandComputation ⃝c Levesque2011 7
Computer Science
It’s not about computers!
Having problems with your PC? Don’t ask a Computer Scientist!
The electronic / physical properties of computers play little or no role in Computer Science
Another analogy to think about: musical instruments vs. music Like music, Computer Science is not about anything physical!
Computer Science is about computation:
a certain form of manipulation of symbols
Modern electronic computers (like an Apple iMac or a Dell PC) just happen to provide a fast, cheap, and reliable medium for computation.
Chapter1:ThinkingandComputation ⃝c Levesque2011 8
Symbols and symbolic structures
• Simplest sort: characters from an alphabet digits: 3, 7, V
letters: a, R, α operators: +, ×, ∩
• String together into more complex ones numerals: 335.42
words: “don’t”
• More complex groupings expressions: 247 + 4(x − 1)3 phrases: “the woman John loved”
• Into truth-valued symbolic structures 3 z!
relations: 247 + 4(x − 1) > 5
sentences: “The woman John loved had brown hair.”
Chapter1:ThinkingandComputation ⃝c Levesque2011 9
Manipulating symbols
The idea: take strings of symbols, break them apart, compare them, and reassemble them according to a recipe called a procedure.
It is important to keep track of where you are, and follow the instructions in the procedure exactly. (You may not be able to figure why you are doing the steps involved!)
The symbols you have at the start are called the inputs. Some of the symbols you end up with will be designated as the outputs.
We say that the procedure is called on the inputs and returns or produces the outputs.
Then construct more complex procedures out of simple procedures. In the next few slides, we will look at an interesting special case:
arithmetic!
Chapter1:ThinkingandComputation ⃝c Levesque2011 10
Arithmetic procedures
Imagine you are explaining to someone (a young child) how to do subtraction:
You might use words like this:
First, you have to subtract 7 from 2. But since 7 is bigger than 2, you need to borrow 10 from the 5 on the left.
That changes the 2 to a 12 and changes the 5 to a 4.
So you subtract 7 not from 2 but from 12, which gives you 5,
and you subtract 1 not from 5 but from 4 which gives you 3. So the answer is 35.
Chapter1:ThinkingandComputation ⃝c Levesque2011 11
A very first procedure
Let’s go back to the most basic form of arithmetic we can imagine: adding two single digit numbers.
What is the procedure there? Here’s one version: call it PROC0
• You will be given two digits as input and return two digits as output. (For example, given 7 and 6 as input, you will return 13 as output.)
• To do so, you will use a table which is on the next page.
• To add the two digits, find the row for the first digit on the table, and the column for the second digit, and return as output the two digit number at the intersection on the table.
Chapter1:ThinkingandComputation ⃝c Levesque2011 12
A table for addition
7 + 6 = 13
0 00010203
1 01020304
2 02030405
3 03040506
4 04050607
5 05060708
6 06070809
040506070809 050607080910 060708091011 070809101112 080910111213 091011121314 101112131415 111213141516 121314151617 131415161718
0123456789
→7 07080910
8 08091011
9 09101112
This is how we all learned multiplication!
Chapter1:ThinkingandComputation ⃝c Levesque2011
Procedure PROC1
We can now start building on procedure PROC0 to do more.
The first thing we will need is to be able to add three digits (which will later allow us to handle carry digits).
Here is a procedure PROC1 that takes three digits a, t, and b, as input, and returns two digits c and s.
1. CallPROC0ontandbtogetuandv.
2. CallPROC0onaandvtogetu′ andv′.
3. Ifu=u′ =0thenreturnwithcas0andsasv′. Ifu=u′ =1thenreturnwithcas2andsasv′. Otherwise, return with c as 1 and s as v′.
Note that we do not say why we do any of this! (But do try it out!) Chapter1:ThinkingandComputation ⃝c Levesque2011
Addition of two numbers
Now that we can follow the PROC1 procedure exactly, we can build on it to do something that we may start to recognize as real addition!
We will construct another procedure PROC2 that can add two strings of digits:
input of PROC2: two strings of digits of the same length x1 x2 … xk
y1y2 …yk
output of PROC2: one string of digits of that length + 1
z0z1z2 …zk
For example, given 747 and 281 (with three digits each), PROC2 will return
1028 (with four digits).
Chapter1:ThinkingandComputation ⃝c Levesque2011 15
The procedure PROC2
1. Start at the right hand side of the inputs. CallPROC1withaasthedigit0, tasxk, andbasyk.
Let zk be the s returned. Hang on to the c for the next step.
2. Now move over one step to the left.
Call PROC1 with a as the c returned in the previous step,
t as xk−1, and b as yk−1.
Let zk−1 be the s returned. Hang on to the c for the next step.
3. Continue this way through all the digits, from right to left, filling out zk−2, zk−3, . . . , z3, z2, z1.
4. Let z0 be the final c returned (from PROC1 with x1 and y1). Note again that the procedure does not explain what it all means.
Chapter1:ThinkingandComputation ⃝c Levesque2011 16
Trying PROC2
We can trace what happens with PROC2 in detail.
Let’s look at what PROC2 does when the xi are 747 and the yi are 281.
1. First, we call PROC1 on 0, 7, 1. It will return 0 and 8. So z3 will be 8.
2. Next, we call PROC1 on 0, 4, 8. It will return 1 and 2. So z2 will be 2.
3. Then, we call PROC1 on 1, 7, 2. It will return 1 and 0. Soz1 willbe0andz0 willbe1.
So PROC2 will return 1028, which is indeed the sum of 747 and 281. So even if you don’t why you are doing all the steps, if you follow the
directions exactly, you will be adding the numbers.
Chapter1:ThinkingandComputation ⃝c Levesque2011 17
Adding a list of numbers
We can now consider a more general procedure PROC3 that uses PROC2 to add any list of numbers n1, n2, . . . , each with any number of digits.
1. Let sum be the single digit 0.
2. Start with the first number n1 and sum. Make sure both of these have the same number of digits by using a PROC4 (it will insert 0’s as necessary to the left). Then call PROC2 on the two resulting numbers, and let sum now be the number returned.
3. Next, do the same thing with the new sum and n2, to produce the next value of sum.
4. Continue this way with the rest of numbers, n3, n4, . . . .
5. Return as output the final value of sum.
Chapter1:ThinkingandComputation ⃝c Levesque2011 18
And on it goes …
Let’s assume we already have procedures to do +, ×, −, ÷ and ≤, as well as string operations (e.g. u ˆv means concatenate strings u and v).
We can use these to define still more complex procedures.
On the next slide, we will consider a mystery procedure called PROCX that takes one positive integer x as input and returns a positive integer y as output.
Try to figure out what this procedure does by trying it out on some sample inputs, for example, 137641.
You should be able to follow the procedure without knowing what exactly you are supposed to be calculating.
Chapter1:ThinkingandComputation ⃝c Levesque2011 19
The PROCX procedure
Group the digits in x into pairs starting from the right. Start with u, v, bot, top, and side all having value 0.
Then, working your way from left to right on the groups in x, repeat the following:
1. Set bot to (bot − u) ˆ(the next group from x)
2. Set side to 2×top
3. Set v to the largest single digit such that v × (side ˆv) ≤ bot 4. Set u to v×(sideˆv)
5. Set top to top ˆv
The answer y to return is the final value of top.
Chapter1:ThinkingandComputation ⃝c Levesque2011 20
Lesson: arithmetic as symbol manipulation
Arithmetic can be built from more primitive symbol manipulations
• starting with very simple operations (such as table lookup), the ability to string and unstring symbols, compare them etc., we can build procedures to do addition
• using these we can build ever more complex procedures, to do multiplication, division, testing for prime numbers, etc.
• using pairs of numbers we can deal with fractions (rational numbers); and using numbers arranged into matrices, we can solve systems of equations, perform numerical simulations, etc.
As we will see in this course, there are also many interesting cases of symbol manipulation that are not numeric!
Chapter1:ThinkingandComputation ⃝c Levesque2011 21
A key observation
You don’t need to know what you’re doing!
To get meaningful answers, you do not have to understand what
the symbols stand for, or why the manipulations are correct.
The symbols can be manipulated completely mechanically and still end up
producing significant and interesting results. This is the trick of computation:
We can get computers to perform a wide variety of very impressive activities precisely because we are able to describe those activities as a type of symbol manipulation that can be carried out purely mechanically.
This “trick” has turned out to be one of the major inventions of the 20th century. And note: It has nothing to do with electronics!
Chapter1:ThinkingandComputation ⃝c Levesque2011 22
But what does this have to do with thinking?
Let us return to what we called the Key Conjecture from earlier: Key Conjecture: thinking can be usefully understood as a
computational process
What does this controversial conjecture amount to?
• not that the brain is something like an electronic computer (which it is in some ways, but in very many other ways is not)
• but that the process of thinking can be usefully understood as a form of symbol processing that can be carried out purely mechanically without having to know what you are doing.
This is what we will explore in this course!
Chapter1:ThinkingandComputation ⃝c Levesque2011 23
Thinking as computation
Some thinking clearly appears to be computation:
• doing math homework • filling out a tax form
• estimating a grocery bill
But much of our thinking seems to have very little to do with calculations or anything numerical.
Unlike arithmetic, thinking seems to involve ideas about an unbounded variety of subjects.
You can think about anything; but it is always about something. So in what sense can thinking be computational?
Chapter1:ThinkingandComputation ⃝c Levesque2011 24
An example
Consider the following:
I know that my keys are either in my coat pocket or on the fridge. That’s where I always leave them.
I feel my coat pocket and I see that there is nothing there.
So my keys must be on the fridge. And that’s where I should go looking.
This is thinking that obviously has nothing to do with numbers.
But it is clearly about something: my keys, pocket, refrigerator.
Can we understand it as a form of computation?
Chapter1:ThinkingandComputation ⃝c Levesque2011 25
(1646-1716)
Co-inventor of the calculus (with Newton)
The first person to seriously consider the idea that ordinary thinking was computation
• the rules of arithmetic allow us to deal with abstract numbers in terms of concrete symbols
manipulations on numeric symbols mirror relationships among the numbers being represented
• the rules of logic allow us to deal with abstract ideas in terms of concrete symbols
manipulations on propositional symbols mirror relationships among ideas being represented
Chapter1:ThinkingandComputation ⃝c Levesque2011 26
Propositions vs. sentences
Definition: A proposition is the idea expressed by a declarative sentence.
for example, the idea that
• my keys are in my coat pocket • dinosaurs were warm-blooded • somebody will fail this course
They are abstract entities (like numbers) but have special properties:
• They are considered to hold or not hold. A sentence is considered to
be true if the proposition it expresses holds.
• They are related to people in various ways: people can believe them,
disbelieve them, fear them, worry about them, regret them, etc. • They are related to each other in various ways: entail, provide
evidence, contradict, etc.
Chapter1:ThinkingandComputation ⃝c Levesque2011 27
A first clue
We do not necessarily need to know what the terms in a sentence mean to be able to think about it.
Example: The snark was a boojum. And now answer the following:
• What kind of thing was the snark?
• Is there anything that was a boojum?
• Was the snark either a beejum or a boojum?
• Given that no boojum is every a beejum, was the snark a beejum?
We can still figure out appropriate answers using simple rules. Compare: the PROCX procedure!
Chapter1:ThinkingandComputation ⃝c Levesque2011 28
Some related thoughts
My keys are in my coat pocket or on the fridge.
Nothing is in my coat pocket. So my keys are on the fridge.
Compare to this:
Henry is in the basement or in the garden.
Nobody is in the basement. So Henry is in the garden.
And compare to this:
Jill is married to George or Jack.
Nobody is married to George. So Jill is married to Jack.
Chapter1:ThinkingandComputation ⃝c Levesque2011 29
It’s all in the form
All three examples are really the same:
Blue thing is green thing or yellow thing.
Nothing is green thing. So blue thing is yellow thing.
It does not matter whether
• blue thing is “my keys” or “Henry” or “Jill”
• green thing is “in my coat pocket or “in the basement” or “married to George”
Note: The thinking is the same!
The only thing that matters is that it is the same term (the blue thing) that is
used in the first and third sentences, etc.
Chapter1:ThinkingandComputation ⃝c Levesque2011 30
Entailment
A collection of sentences, S1, S2, . . . Sn entail a sentence S if the truth of S is implicit in the truth of the Si.
No matter what the terms in the Si really mean, if the Si sentences are all true, then S must also be true.
For example, Entails:
The snark was a boojum.
and Entails:
My keys are in my coat pocket or on the fridge. Nothing is in my coat pocket.
My keys are on the fridge.
Chapter1:ThinkingandComputation
⃝c Levesque2011 31
Something was a boojum.
Can this be how we think??
Suppose we are told at a party: George is a bachelor. Here is what is entailed:
• Somebody is a bachelor.
• George is either a bachelor or a farmer.
• Not everyone is not a bachelor.
• It is not the case that George is not a bachelor.
All true, but very very boring!
But when we think about it, we think about
• George (who we may know a lot about)
• being a bachelor (which we may know a lot about)
So our thinking appears to depend on what the terms mean! Chapter1:ThinkingandComputation ⃝c Levesque2011 32
Using what you know
We must consider the entailments of not only George is a bachelor, but this + a large collection of other sentences we might already know:
George was born in Boston, collects stamps. A son of someone is a child who is male. George is the only son of Mary and Fred.
A man is an adult male person.
A bachelor is a man who has never been married.
A (traditional) marriage is a contract between a man and a woman, enacted by a wedding and dissolved by a divorce. While the contract is in effect, the man (called the husband) and the woman (called the wife) are said to be married.
A wedding is a ceremony where … bride … groom … bouquet …
The terms like “George” and “bachelor” and “person” and “stamps” appear in many places and link these sentences together.
Chapter1:ThinkingandComputation ⃝c Levesque2011 33
The web of belief
swas sin s, … …
Each sentence we believe is linked to many others by virtue of the terms that appear in them.
George born Boston Fred
sof sand s
It is the job of logic to crawl over this web looking for connections among the terms.
swho has never been
Chapter1:ThinkingandComputation ⃝c Levesque2011
son Mary child
ofsomeoneisa whois
adult male
A sisanSs s s
marriage contract married
ss @s A isa … … saidtobe
Using what you know
When we include all these other facts, here are some entailments we get:
• George has never been the groom at a wedding. • Mary has an unmarried son born in Boston.
• No woman is the wife of any of Fred’s children.
The conclusions are much more like those made by ordinary people. We find where the same term appears (like we did with the blue
thing, the green thing etc.).
We then apply simple rules of logic to draw conclusions.
We still do not need to know what “George” or “bachelor” means! Now, the big step:
Imagine drawing conclusions from millions of such facts. Chapter1:ThinkingandComputation ⃝c Levesque2011 35
Two hypotheses
1. Much of the richness of meaning that we experience during thinking may be accounted for in terms of simple symbolic manipulations over a rich collection of represented propositions
2. To build computers systems that are versatile, flexible, modifiable, explainable, . . . it is a good id
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com