Tuesday 2/11
Computability
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)
Notes
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 is Machine Functionalism: Mental states are functional states of the organism. Understood in terms of the theory we began developing today, this yields computationalism--roughly, the view that mental states are computational states of the organism's underlying neurological processes.
We've also found that 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. If so, then it is plausible 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.
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 machine?
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 earthshattering. 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 mechanical means to determine whether a solution exists for an equation, Turing constructed a model of a mechanical method (an "effective procedure", as we will call it) we know today as the Turing Machine.
Today I explained the operations of the Turing Machine and we built a flow-graph for a Turing Machine that would compute the function f(n)=n+4 and another which would compute the general function of binary addition for the positive whole numbers:
f(n,m) = n+m, for all natural numbers n,m > 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 (machine functionalism) requires. Bear in mind that we are breaking down arithmetical calculations to their absolute simplest, whereby n-X's on a tape represent the number n, and we compute 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 explore the necessary limitations on TM-computation.