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: In addition, to be complete, a computation history must be finite and 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.
, a configuration is simply the current state of the machine, together with the remaining input.
The first configuration must be the initial state of
The final configuration must have the empty string
has accepted or rejected the input depends on whether the final state is an accepting state.
[1] 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
is the current state of the machine, represented in some way that's distinguishable from the tape language, and where
is the initial state of the Turing machine.
The machine's state in the final configuration must be either
is a valid successor to configuration
which manipulates the tape and moves the read/write head in a way that produces the result in
[2] Computation histories can be used to show that certain problems for pushdown automata are undecidable.
This is because the language of non-accepting computation histories of a Turing machine
is a context-free language recognizable by a non-deterministic pushdown automaton.
We encode a Turing computation history
, as discussed above, and where every other configuration is written in reverse.
Before reading a particular configuration, the pushdown automaton makes a non-deterministic choice to either ignore the configuration or read it completely onto the stack.
In addition, the automaton verifies that the first configuration is the correct initial configuration (if not, it accepts) and that the state of the final configuration of the history is the accept state (if not, it accepts).
[3] This same trick cannot be used to recognize accepting computation histories with an NPDA, since non-determinism could be used to skip past a test that would otherwise fail.
A linear-bounded Turing machine is sufficient to recognize accepting computation histories.
This result allows us to prove that
, the language of pushdown automata which accept all input, is undecidable.
, we can form the pushdown automaton
which accepts non-accepting computation histories for that machine.