Turing machine
|
JC pontificates about technology
An occasional series.
|
Turing machine
/ˈtjʊərɪŋ məˌʃiːn/ (n.)
A hypothetical computing machine which by using a predefined set of rules, can process symbols to determine a result from a set of input variables.
These days, a computer, but as Daniel Dennett ably demonstrated, any process which runs an algorithm, regardless of its substrate is a Turing machine:
Three key features of algorithms will be important to us, and each is somewhat difficult to define. Each, moreover, has given rise to confusions (and anxieties) that continue to beset our thinking about Darwin’s revolutionary discovery, so we will have to revisit and reconsider these introductory characterizations several times before we are through:
(1) substrate neutrality: The procedure for long division works equally well with pencil or pen, paper or parchment, neon lights or skywriting, using any symbol system you like. The power of the procedure is due to its logical structure, not the causal powers of the materials used in the instantiation, just so long as those causal powers permit the prescribed steps to be followed exactly.
(2) underlying mindlessness: Although the overall design of the procedure may be brilliant, or yield brilliant results, each constituent step, as well as the transition between steps, is utterly simple. How simple? Simple enough for a dutiful idiot to perform—or for a straightforward mechanical device to perform. The standard textbook analogy notes that algorithms are recipes of sorts, designed to be followed by novice cooks. A recipe book written for great chefs might include the phrase “Poach the fish in a suitable wine until almost done,” but an algorithm for the same process might begin, “Choose a white wine that says ‘dry’ on the label; take a corkscrew and open the bottle; pour an inch of wine in the bottom of a pan; turn the burner under the pan on high; ...” —a tedious breakdown of the process into dead-simple steps, requiring no wise decisions or delicate judgments or intuitions on the part of the recipe-reader.
(3) guaranteed results: Whatever it is that an algorithm does, it always does it, if it is executed without misstep. An algorithm is a foolproof recipe.
Named after Alan Turing, the computing pioneer and Bletchley Park codebreaker who thought them, and the related Turing test, up.