SCXT 350

Final Exam

Name _____________________________________

We have covered considerable ground in the last semester. The primary question under discussion has been "Is intelligent action computable?". Along the way of discussing that thesis, we have learned something about computation, something about symbolic and connectionist approaches to artificial intelligence, something about language, and have heard from some of those who agree and some of those who disagree with the thesis. The exam is organized along the same lines of the course. We begin with the question of computation.

Wednesday, Dec. 18, 4:00 PM

200 pts.

I. Computation

What does it mean that intelligent action is computable? What is involved in computation? We have looked at several formal and informal models.

a. (15 pts.) From the first part of the course, sketch a model for a computer, labeling and describing the parts.

b. (10 pts.) What is an algorithm?

c. (10 pts.) What does a programming language do? What does a program do?

c. (15 pts.) We looked at the programming language LISP. In that language

i. Write an expression for (3 + 2) * (7 – 4)

ii. Write an expression to return the third item in a list

iii. Write a function which will accept two numbers and return the larger. For example, (mymax 4 7) should return 7.

d. (10 pts.) Perhaps the simplest useful formal model for computation is the finite state automaton. Describe the elements of a finite state automaton, and say what conditions must be true for a FSA to accept a string of characters

e. (10 pts.) There are some basic things that a FSA can not do, but a push-down automaton can. Give an example and say what a PDA has that gets around the problem.

f. (10 pts.) PDA's can generate and recognize a sizable collection of formal languages. Give an example of a formal language and say what makes it different from a natural language (such as Chinese, English, or Welsh).

g. (5 pts.) We think of Turing Machines as being the most powerful model for computation. This is a statement of what hypothesis?

h. (5 pts.) We can write in Lisp (or nearly any other programming language) a program that simulates a Turing Machine. What does this say about Lisp?

II. Symbolic and Connectionist AI.

a. (15 pts.) What characterizes symbolic AI?

b. (15 pts.) What characterizes connectionist AI?

c. (15 pts.) We have examined a number of knowledge representation schemes in this term. Pick two of them and describe them.

d. (15 pts.) Problem solving frequently involves the selection of suitable operators to move us from one problem state to another. Consider the problem of getting home for the semester break. While giving a definition of the terms state, operator, precondition, and postcondition, describe what the states, operators, preconditions, and postconditions would be for the getting-home problem.

III. Philosophy (30 pts.)

Consider the Descartes, Turing, Marr, Newell and Simon, and Searle papers in the coursepack to be a time-constrained discussion starting with Descartes and continuing through Searle. In the form of an introduction to the coursepack, outline (in essay form, of course) the main issues raised in this conversation. Be sure to address in your introduction (in addition to other issues you may wish to discuss) the notion that intelligent action is computable. Two exam pages are provided for this major essay question.

(work page for problem III)

IV. Finally, language. We did not have as much time with this as we would like, but it is of central importance (whichever side of the semester's question you find yourself).

a. (10 pts.) Given the grammar

S -> NP | VP

NP -> DET N

N -> ADJ N | N

DET -> a | the

ADJ -> big | small | mild | fierce | red

N -> cat | dog | ball

VP -> V NP

V -> chased | bit | found

Write a (small) sentence that fits this grammar, and demonstrate that it fits by giving either a parse tree or a derivation.

b. (10 pts.) What is the importance of other people in a child's language development?