Computation history explained
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.
Finite State Machines
, a configuration is simplythe current state of the machine, together with the remaining input. The first configuration must be the initial state of
and the complete input. A transition from a configuration
toa configuration
is allowed if
forsome input symbol
and if
has a transition from
to
on input
. The finalconfiguration must have the empty string
as its remaininginput; whether
has accepted or rejected the input dependson whether the final state is an accepting state.
[1] 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
...0011010101q00110101010...
where
is the current state of the machine, represented in someway that's distinguishable from the tape language, and where
ispositioned immediately before the position of the read/write head.
Consider a Turing machine
on input
. The firstconfiguration must be
, where
is the initial state of the Turing machine. The machine's state in the finalconfiguration must be either
(the accept state) or
(the reject state). A configuration
is a valid successorto configuration
if there's a transition from the state in
to the state in
which manipulates thetape and moves the read/write head in a way that produces the result in
.
[2] Decidability results
Computation histories can be used to show that certain problems forpushdown automata are undecidable. This is because the language ofnon-accepting computation histories of a Turing machine
on input
is a
context-free language recognizable by anon-deterministic pushdown automaton.
We encode a Turing computation history
as thestring
, where
is the encoding of configuration
, as discussed above, and whereevery other configuration is written in reverse. Before reading a particularconfiguration, the pushdown automaton makes a non-deterministic choiceto either ignore the configuration or read it completely onto the stack.
- If the pushdown automaton decides to ignore the configuration, it simply reads and discards it completely and makes the same choice for the next one.
- If it decides to process the configuration, it pushes it completely onto the stack, then verifies that the next configuration is a valid successor according to the rules of
. Since successive configurations are always written in opposite orders, this can be done by, for each tape symbol in the new configuration, popping off a symbol from the stack and checking if they're the same. Where they disagree, it must be accountable for by a valid transition of
. If, at any point, the automaton decides that the transition is invalid, it immediately enters a special accept state which ignores the rest of the input and accepts at the end.
In addition, the automaton verifies that the first configuration is the correctinitial configuration (if not, it accepts) and that the state of the finalconfiguration of the history is the accept state (if not, it accepts). Sincea non-deterministic automaton accepts if there's any valid way for it to accept,the automaton described here will discover if the history is not a validaccepting history and will accept if so, and reject if not. [3]
This same trick cannot be used to recognize accepting computation historieswith an NPDA, since non-determinism could be used to skip past a test that wouldotherwise fail. A linear-bounded Turing machine is sufficient to recognizeaccepting computation histories.
This result allows us to prove that
, the languageof pushdown automata which accept all input, is undecidable. Supposewe have a decider for it,
. For any Turing machine
and input
, we can form the pushdown automaton
which accepts non-accepting computation histories for thatmachine.
will accept if and only if there are noaccepting computation histories for
on
; thiswould allow us to decide
, which we know to be undecidable.
Notes and References
- Book: Christine L. Mumford. Lakhmi C. Jain. Computational Intelligence: Collaboration, Fusion and Emergence. 25 March 2012. 2009. Springer. 978-3-642-01798-8. 337.
- Book: Andreas Blass. Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday. 25 March 2012. 22 October 2010. Springer. 978-3-642-15024-1. 468.
- Book: Lenore Blum. Complexity and real computation. Complexity and Real Computation . 1998. Springer. 978-0-387-98281-6. p. 31.
