In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and particularly about the undecidability of various formal languages.
Formally, a computation history is a (normally finite) sequence of configurations of a formal automaton. Each configuration fully describes the status of the machine at a particular point. To be valid, certain conditions must hold:
- the first configuration must be a valid initial configuration of the automaton and
- each transition between adjacent configurations must be valid according to the transition rules of the automaton.
In addition, to be complete, a computation history must be finite and
- the final configuration must be a valid terminal configuration of the automaton.
The definitions of "valid initial configuration", "valid transition", and "valid terminal configuration" vary for different kinds of formal machines.
A deterministic automaton has exactly one computation history for a given initial configuration, though the history may be infinite and therefore incomplete.
Read more about Computation History: Finite State Machines, Turing Machines
Famous quotes containing the words computation and/or history:
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“The history of our era is the nauseating and repulsive history of the crucifixion of the procreative body for the glorification of the spirit.”
—D.H. (David Herbert)