Problem Set 02

(Once again, be sure to review the instructions before getting started!)

1. The Turing Test

Consider the following quotes about Turing's "Computing Machinery and Intelligence" and the Turing Test:

In fact Turing believed, or at very least saw no reason not to believe, much more than this: that there would, eventually, turn out to be no essential difference between what could be achieved by a human intellect in, say, mathematics, and what could be achieved by a machine. The 1950 paper was intended not so much as a penetrating contribution to philosophy but as propaganda. Turing thought the time had come for philosophers and mathematicians and scientists to take seriously the fact that computers were not merely calculating engines but were capable of behaviour which must be accounted as intelligent; he sought to persuade people that this was so. He wrote this paper--unlike his mathematical papers--quickly and with enjoyment. I can remember him reading aloud to me some of the passages--always with a smile, sometimes with a giggle. Some of the discussions of the paper I have read load it with more significance than it was intended to bear. I shall discuss it no further.

Robin Gandy, "Human versus Machine Intelligence." In P. Millican and A. Clark, eds. 1996. Machines and Thought: The Legacy of Alan Turing, Volume 1. Oxford: Oxford University Press. p. 125.

Turing cast his test in terms of simulation or imitation: a non-human system will be deemed intelligent if it acts so like an ordinary person in certain respects that other ordinary people can't tell (from these actions alone) that it isn't one. But the imitation idea itself isn't the important part of Turing's proposal. What's important is rather the specific sort of behavior that Turing chose for his test: he specified verbal behavior. A system is surely intelligent, he said, if it can carry on an ordinary conversation like an ordinary person (via electronic means, to avoid any influence due to appearance, tone of voice, and so on).

This is a daring and radical simplification. There are many ways in which intelligence is manifested. Why single out talking for special emphasis? Remember: Turing didn't suggest that talking in this way is required to demonstrate intelligence, only that it's sufficient. So there's no worry about the test being too hard; the only question is whether it might be too lenient. We know, for instance, that there are systems that can regulate temperatures, generate intricate rhythms, or even fly airplanes without being, in any serious sense, intelligent. Why couldn't the ability to carry on ordinary conversations be like that?

Turing's answer is elegant and deep: talking is unique among intelligent abilities because it gathers within itself, at one remove, all others. One cannot generate rhythms or fly airplanes "about" talking, but one certainly can talk about rhythms and flying--not to mention poetry, sports, science, cooking, love, politics, and so on--and, if one doesn't know what one is talking about, it will soon become painfully obvious. Talking is not merely one intelligent ability among others, but also, and essentially, the ability to express intelligently a great many (maybe all) other intelligent abilities. And, without having those abilities in fact, at least to some degree, one cannot talk intelligently about them. That's why Turing's test is so compelling and powerful.

John Haugeland, 1997. "What is Mind Design?" In J. Haugeland, ed. Mind Design II: Philosophy, Psychology, and Artificial Intelligence. Cambridge, Mass.: MIT Press, A Bradford Book. pp. 3-4.

The Turing test in unadulterated, unrestricted from [sic], as Turing presented it, is plenty strong if well used. I am confident that no computer in the next twenty years is going to pass an unrestricted Turing test. They may well win the World Chess Championship or even a Nobel Prize in physics, but they won't pass the unrestricted Turing test. Nevertheless, it is not, I think, impossible in principle for a computer to pass the test, fair and square. I'm not running one of those A priori "computers can't think" arguments. I stand unabashedly ready, moreover, to declare that any computer that actually passes the unrestricted Turing test will be, in every theoretically interesting sense, a thinking thing.

Daniel Dennett, 1998. "Can Machines Think?" In D.C. Dennett, ed. Brainchildren: Essays on Designing Minds. Cambridge, Mass.: MIT Press, A Bradford Book. p. 20.

In a long essay, explain the Turing Test for machine intelligence. Is the perfect simulation of intelligence intelligence? Why or why not? (20)

2. The Subtractor Function

Consider the following function:

f(n) = n + 2, for all natural numbers n > 0.

Show that f is Turing Machine Computable by constructing a Turing Machine that computes it--i.e., give a flow graph of the instruction set to solve the function for any such n. (10)

3. The Trinary Adder

Show that the following function is Turing Machine Computable by constructing a Turing Machine that computes it--i.e., give a flow graph of the instruction set to solve the function for any natural numbers n, m, and p not including 0. (20)

f(n,m,p) = n + m + p

Extra Credit: The Ugly Doubler

Turing's Theorem--that there exists a Turing Machine that can compute any function computable by any Turing Machine--demonstrates that for any given Turing Machine computable function there are at least two Turing Machine's that compute it. Indeed, we can prove that there are infinitely many Turing Machines that compute any Turing Machine computable function.

Of any two Turing Machines TM-1 and TM-2 that compute the same function, let us say that TM-1 is more elegant than TM-2 iff TM-1 requires fewer states in its flow-graph than TM-2. We might add that TM-2 is uglier than TM-1 if it requires more states to do the same thing.

The Ugly Doubler (pdf) is ugly indeed. It requires a total of 17 states to compute the function f(n)=2n, x>0. Write the flow graph of a less ugly Turing Machine that computes the same function. Note that some of the states are obviously eliminable, while more dramatic cuts might be made by reconsidering the basic strategy. The most elegant solution (a mere 6 states!) of the problem I've yet seen is the Ariel McCree Solution:

Whatever your solution, be sure to run your Turing Machine on limiting input (x=1) as well as other test cases (n=3, say) to check whether it works in general! (20)