Turing machines: abstract or real-world machines that operate by digitally computing the values of recursive functions.
ELABORATION
What is a Turing machine, and what are its operations (Turing, 1936/1937, 1950; Church, 1937)?
Here’s a compact and elegant way of characterizing them:
No human being can write fast enough, or long enough, or small enough, to list all members of a… [d]enumerably infinite set [e.g., the positive integers] by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain [d]enumerably infinite sets: They can give explicit instructions for determining the nth member of the set for an arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols. The problem will remain, that for all but a finite number of values of n it will be physically impossible for any human or any machine to actually carry out the computation, due to limitations on the time available for computation, and on the speed with which single steps of the computation can be carried out, and on the amount of matter in the universe which is available for forming symbols. But it will make for clarity and simplicity if we ignore these limitations, thus working with a notion of computability which goes beyond what actual men or machines can be sure of doing…. The notion of computation can be made precise in many different ways, corresponding to different possible answers to such questions as the following. “Is the computation to be carried out on a linear tape, or on a rectangular grid, or what? If a linear tape is used, is the tape to have a beginning but no end, or is it to be endless in both directions? Are the squares into which the tape is divided to have addresses (like addresses of houses on a street) or are we to keep track of where we are by writing special symbols in suitable squares (as one might mark a trail in the woods by marking trees)? And so-on…. Since there is no end to the possible variations in detailed characterizations of the notions of computability and effectiveness, one must finally accept or reject the thesis [aka “Church’s thesis,” aka “the Church-Turing thesis”] … that the set of functions computable in our sense [i.e., the set of recursive functions] is identical with the set of functions that men or machines would be able to compute by whatever effective method, if limitations on time, speed, and material were overcome. (Boolos and Jeffrey, 1989: pp. 19-20, square-bracketted material added)
And here’s a diagram of one possible kind of Turing machine:
So in other and fewer words, a Turing machine is a digital computer, and its operations are all and only the computations that fall within the scope of recursive functions.
Recursive functions, in turn, are step-by-step algorithms, routines, or rule-governed sequences, such that precisely the same algorithm/routine/rule-governed sequence is applied to the result of the preceding step, in a denumerable (countable) sequence, up to some arbitrarily-fixed terminal step.
certain functions are not computable, and that certain [d]enumerable sets are not effectively (mechanically) [d]enumerable—even if physical limitations on time, speed, and amount of material could somehow be overcome. (Boolos and Jeffrey, 1989: p. 19, square bracketting and underlining added)
In particular, it’s logically demonstrable that truth and proof in Peano arithmetic, and also in classical first-order polyadic predicate logic, are not computable (Boolos and Jeffrey, 1989: chs. 10, 15, 16, 21, 22, 28; see also the entry on “Gödel’s incompleteness theorems”).
And more generally, functions over non-denumerable sets (for example, the real numbers) are not computable, precisely because they’re not recursive functions.
Therefore, digital computation has inherent formal limits.
REFERENCES
(Boolos and Jeffrey, 1989). Boolos, G. and Jeffrey, R. Computability and Logic. 3rd edn., Cambridge: Cambridge Univ. Press.
(Church, 1937). Church, A. “Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem.” Journal of Symbolic Logic 2: 42–43.
(Turing, 1936/1937). Turing, A. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society 42: 230-265, with corrections in 43: 644-546.
(Turing, 1950). Turing, A. “Computing Machinery and Intelligence.” Mind 59: 433–460.
Robert Hanna
If you feel so inclined, please feel free to show your support for Robert via his Patron page (https://www.patreon.com/philosophywithoutborders) or purchase his recently published book, The Fate of Analysis (2021).
The Fate of Analysis (2021)
Robert Hanna’s twelfth book, The Fate of Analysis, is a comprehensive revisionist study of Analytic philosophy from the early 1880s to the present, with special attention paid to Wittgenstein’s work and the parallels and overlaps between the Analytic and Phenomenological traditions.
By means of a synoptic overview of European and Anglo-American philosophy since the 1880s—including accessible, clear, and critical descriptions of the works and influence of, among others, Gottlob Frege, G.E. Moore, Bertrand Russell, Alexius Meinong, Franz Brentano, Edmund Husserl, The Vienna Circle, W.V.O. Quine, Saul Kripke, Wilfrid Sellars, John McDowell, and Robert Brandom, and, particularly, Ludwig Wittgenstein—The Fate of Analysis critically examines and evaluates modern philosophy over the last 140 years.
In addition to its critical analyses of the Analytic tradition and of professional academic philosophy more generally, The Fate of Analysis also presents a thought-provoking, forward-looking, and positive picture of the philosophy of the future from a radical Kantian point of view.
