更改

{{Automata theory}}

{{Automata theory}}

A '''Turing machine''' is a [[mathematical model of computation]] that defines an [[abstract machine]],<ref>Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref> which manipulates symbols on a strip of tape according to a table of rules.<ref>Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> Despite the model's simplicity, given any [[computer algorithm]], a Turing machine capable of simulating that algorithm's logic can be constructed.<ref>Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>

A '''Turing machine''' is a [[mathematical model of computation]] that defines an [[abstract machine]],<ref name=":3">Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref> which manipulates symbols on a strip of tape according to a table of rules.<ref name=":4">Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> Despite the model's simplicity, given any [[computer algorithm]], a Turing machine capable of simulating that algorithm's logic can be constructed.<ref name=":5">Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>

 

 

 

The machine operates on an infinite<ref name=":0">Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref name=":1">Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref name=":2">This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>

The machine operates on an infinite<ref name=":0">Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref name=":1">Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref name=":2">This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>