Lectures on the Philosophy of Mathematics

by Joel David Hamkins

The universal Turing machine is a Turing machine that accepts as input another Turing-machine program e and input n, and computes the result φe(n) of that program on that input. For example, perhaps the universal machine inspects the program e and simulates the operation of e on input n. The existence of universal Turing machines shows that having arbitrarily large mental capacity, as measured in the number of states, is not required to undertake arbitrary computational tasks. After all, the universal computer has only a certain fixed finite number of states (and not necessarily a very large one), and these suffice for it to carry out in principle any computational procedure if one should only write out the instructions for that procedure on the tape. Turing conceived of the machine state as analogous to a human mental state, and in this sense, the existence of universal machines show that a bounded mind—one with only finitely many mental states (and not necessarily very many)—can nevertheless undertake the same computational tasks as larger minds, if provided with suitable instructions and enough note-taking space.