Readings
Texts
- A.M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem (Optional)
- David Hilbert, Mathematical Problems (Optional)
- Boolos & Jeffrey, "Computability and Logic" (excerpt, pdf)
Handouts
Synopsis
Today we took up the theoretical foundation of computation and, therewith, computationalism.
Rehearsing our progress thus far, we've found that Philosophy has largely settled on physicalism as the most defensible solution to the mind-body problem: Every mental event is some physical event. The version of physicalism we take as our starting point this semester as a result, note, of the Multiple Realizability Argument is Functionalism: Mental states are functional states of the organism. Of course, it is one thing to conclude the mind is what the brain does, and quite another to draw the much more restricted conclusion that what the brain is doing specifically is performing computations, for which conclusion we appealed to the mathematical history we developed starting with Galileo and Hobbes. Understood in terms of the theory we began developing today, this yields computationalism--roughly, the view that mental states are specifically the computational states of the organism's underlying neurological processes.
So mathematics, in discovering that the very same symbols can be about--or be applied to--very different things in the world equally well, has postulated that thought itself is nothing more than the rule-governed manipulation of strings of symbols. It is plausible, then, to suppose that we can eventually figure out how to build a mind, thereby meeting the engineering obligato of Dretske's Dictum so as to come to understand the mind. That is, we can--in principle, at least--build a machine with a mind--the long sought goal of Artificial Intelligence, provided that computationalism is the correct solution to the Mind-Body problem.
Now recall that our optimism about understanding the mind by figuring out how to build an intelligent machine is considerably tempered by the fact that we are forced to confront two very difficult questions:
- What is intelligence?
- What is a computation?
As we've seen, Turing provides a clever answer to the first question. We don't need to know what intelligence is to be able to test for it. However we define intelligence, the Turing Test constitutes a behavioral test for intelligence by proposing that the perfect imitation of intelligence just is intelligence. This is clever, but not earth-shattering. It is certainly open to dispute, as we have seen in our preliminary analysis of the test.
We fully grasp Turing's genius, however, when we consider his answer to the second question. In finding an answer to Hilbert's challenge of discovering whether there was some effective procedure or mechanical means to determine whether a solution exists for an equation, Turing constructed a model of an effective procedure we know today as the Turing Machine. What's remarkable is that Turing developed the theory of computation simply as a necessary step to proving undecidability for arithmetic, Hilbert's original challenge! Computability wasn't even Turing's main goal, but it became, of course, overwhelmingly important.
Today I explained the operations of the Turing Machine and we built a flow-graph for a Turing Machine that would compute the arithmetical function:
f(n) = n+1, for all natural numbers n > 0.
This is the so-called successor function, and we found that the flow-graph for it was relatively simple, consisting as it did of just two states.
Generalizing, we considered the binary addition function:
f(n,m) = n+m, for all natural numbers n,m > 0.
Here the problem was having joined two the two strings of n "X's" and m "X's" by putting an "X" in the blank cell between them, we have one extra "X" on the resulting string! So we must either nibble at the start of the computation, or nibble at the end. Contrasting the two strategies we found that they required exactly the same number of states (4), which shows the Turing Machines are non-unique. Indeed, where there exists one TM that computes a given function, there exists infinitely (but countably) many TM's that compute the function. This introduces the idea of elegance, where we say that the TM that computes a given function in the least number of states is the most elegant. Clearly, then, the left-nibble and right-nibble TM's computing binary addition are equally elegant.
We closed by inviting Matt to the board to show that trinary addition is TM-computable. Thus,
f(n,m,r) = n+m+r, for all natural numbers n, m, r > 0.
To be sure, this probably all seems very difficult, abstract, and perhaps even entirely opaque. Nevertheless, it is important you grapple with programming Turing Machines to get a sense of what computionalism requires. Bear in mind that we are breaking down arithmetical calculations to their simplest procedural form, whereby n-"X's" on a tape represent the number n, and we compute arithmetical functions by manipulating strings of X's on an indefinitely long tape.
We will continue our examination of Turing Machines next time and discuss one of the most startling results of the theory--the existence, namely, of the Universal Turing Machine. Along the way, we will also learn why there was so much initial enthusiasm for the prospects of artificial intelligence even as we developed a comprehensive theory outlining the necessary limitations on TM-computation.