Turing Machines
Computation histories are more commonly used in reference to Turing machines. The configuration of a single-tape Turing machine consists of the contents of the tape, the position of the read/write head on the tape, and the current state of the associated state machine; this is usually written
where is the current state of the machine, represented in some way that's distinguishable from the tape language, and where is positioned immediately before the position of the read/write head.
Consider a Turing machine on input . The first configuration must be, where is the initial state of the Turing machine. The machine's state in the final configuration must be either (the accept state) or (the reject state). A configuration is a valid successor to configuration if there's a transition from the state in to the state in which manipulates the tape and moves the read/write head in a way that produces the result in .
Read more about this topic: Computation History
Famous quotes containing the word machines:
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)