Assignment 1

The assignment was worth 10 pts overall.

3 pts (Turing's paper) Mostly this was up to you, but there a few things I was looking for:
- Did you comment on more than one objection/refutation? By "comment", I mean: Did you offer an opinion as to the validity and have reasons for your opinion?
- Many people failed to address the additional questions, concerning new objections that you might raise yourself or Turing's claim regarding the chance that a machine would successfully play the imitation game by 2000. I didn't take off if you skipped these two if you had a well-written response to the Turing paper.
- Many people felt that the argument of continuity of the nervous system and the argument from consciousness were the most persuasive.
- Yes, it's a little weird that Turing mentioned ESP, but it was a different time.
1 pt I didn't weight this question too heavily because it didn't require an extensive response. As it turns out, many people did not understand what intractable and undecidable meant. For people in CS 250, you're not required to have theory (CS 280) as a prerequisite, so I wasn't too stringent about this. However, if you don't understand the terms, you probably won't answer the question correctly. Prerequisites, there's an easy way to find out the definition of unknown terms: ask.
No, the existence of intractable or undecidable problems does not mean that AI is impossible. However, it does mean that AI systems should avoid tackling intractable problems "head-on" -- don't try to build an AI system that optimally solves the traveling salesman problem (TSP). Instead, look for a good approximation, perhaps using heuristic rules. Note that people generally don't solve intractable problems either. If it's reasonable to model the brain as a Turing machine (even if that means every neuron is modeled by a Turing machine), then brains are of course bound by the same limitations as Turing machines.
2 pts There was more leeway in this question than most people thought. Some people read the quote from Herb Simon in the reading and recast it to answer this question: Yes, the latter statement is true and no, it doesn't imply the former. Of course, Herbie (not the Love Bug, the other Herbie) had definitions in mind for intelligent and tell. You might have different definitions for these terms which would lead to different answers.
If we take tell quite literally, then it's true that computers can only do what their programmers tell them. Of course, their programmers might tell them to adapt to new situations, or learn by observing others, and thus they could behave in unexpected ways.
2 pts I was a little surprised by the answers to this question. Very, very few people made any connection between this question and the previous question, which was the whole point. Many people, failing to see the connection, gave answers that were logically inconsistent across the two questions. The most common pair of responses was to say:
1. Computers can't be intelligent because they can only do what their programmers tell them.
2. Animals can be intelligent because even though they have genes (instructions), they are influenced by their environment and adapt to it.
You can either have your cake, or you can eat it. Pick one. Perhaps there was confusion because essentially all animals are adaptable to their surroundings (and profoundly so), but many (most?) computer programs do not incorporate adaptability beyond simple branching. You could give different answers to 1.9 and 1.10 if you argued that the mechanism for encodng instructions make a difference, but nobody did.

Although genes specify how animals are constructed, they encode adaptability as well. Thus, animals (including people) are endowed with the ability to adapt to their environment. This ability is so strongly expressed that their often substantial differences between animals with identical genes.
2 pts I don't want to scare anyone (well, okay, I want to scare people a little bit), but if you had trouble with this problem, you might not have the right preparation for the class. This problem was mostly intended as the weakest of checks that you knew something about functional programming/Lisp and understood Chapter 2. Some people had great difficulty with this problem, and almost everyone had solutions that were, ahem..., not stylish.
1. The problem with this function is the list with nil's removed is never passed as an argument to apply(). Next, you need to know that the value of a function is the value of the last form in the function body. In the broken code, remove() is called on one line and the addition is performed on the next line. Since the application of the + function is the last form, that's what gets returned. The correct code would be:
```
(defun summit (lst)
```
```
   (apply #'+
```
```
      (remove nil lst)))
```
  (Why use apply() here? Why not just + ?)
  
  A very common problem here was that people said, "The list isn't actually changed by remove(), so apply() is working with the original (nil's included) list." This isn't actuallywrong, but it hints that people are taking the wrong perspective. Thiws furer evidenced by the proposed solution -- just setf the list to the value of the remove function:
```
(setf lst (remove nil lst))
```
  Yikes. This is not all functional, and not really necessary becuase you can just the pass the value of the remove() function directly to apply(), as in the solution. This time, I didn't dock anybody points for this. Next time....
2. Many people struggled with this one. Several people thought that the function included the wrong number of parentheses, but this wasn't the problem. The syntax for let should look familiar, but if it isn't look it up -- let can be your friend.
  The problem in a nutshell is this: nil is a list, and its car() and cdr() are both nil. Thus, there is no base case for the recursion. The code "cdr's down the list" (to use the Lisp terminology), but doesn't recognize that it eventually cdr's to the null list, and so loops forever. The correct function is:
```
		(defun summit (lst)
```
```
			(if (null lst)
```
```
				0
```
```
				(let ((x (car lst)))
```
```
					(if (null x)
```
```
						(summit (cdr lst))
```
```
						(+ x (summit (cdr lst)))))))
```
  Some people moved the check for a null list into the body of the let, but this has two problems. First, it goes against the standard recursion template where one handles the base case before taking the recursive step. Second, it wastes time and resources. If the list is null, there's no sense assigning the car of the list to a variable for possible later testing.