World Library  
Flag as Inappropriate
Email this Article

Computation history

Article Id: WHEBN0007620568
Reproduction Date:

Title: Computation history  
Author: World Heritage Encyclopedia
Language: English
Subject: Post correspondence problem, Theory of computation, Context-free grammar
Collection: Theory of Computation
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Computation history

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.

Contents

  • Finite State Machines 1
  • Turing Machines 2
    • Decidability results 2.1
  • References 3

Finite State Machines

For a finite state machine M, a configuration is simply the current state of the machine, together with the remaining input. The first configuration must be the initial state of M and the complete input. A transition from a configuration (S,I) to a configuration (T,J) is allowed if I=aJ for some input symbol a and if M has a transition from S to T on input a. The final configuration must have the empty string \epsilon as its remaining input; whether M has accepted or rejected the input depends on 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 q is the current state of the machine, represented in some way that's distinguishable from the tape language, and where q is positioned immediately before the position of the read/write head.

Consider a Turing machine M on input w. The first configuration must be q_0 w_0 w_1 ..., where q_0 is the initial state of the Turing machine. The machine's state in the final configuration must be either q_a (the accept state) or q_r (the reject state). A configuration c_{i+1} is a valid successor to configuration c_i if there's a transition from the state in c_i to the state in c_{i+1} which manipulates the tape and moves the read/write head in a way that produces the result in c_{i+1}.[2]

Decidability results

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 M on input w is a context-free language recognizable by a non-deterministic pushdown automaton.

We encode a Turing computation history c_0,c_1,...,c_n as the string C_0 \# C^r_1 \# C_2 \# C^r_3 \# ... \# C_n, where C_i is the encoding of configuration c_i, 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.

  • 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 M. 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 M. 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 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). Since a 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 valid accepting history and will accept if so, and reject if not. [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 ALL_{PDA}, the language of pushdown automata which accept all input, is undecidable. Suppose we have a decider for it, D. For any Turing machine M and input w, we can form the pushdown automaton P which accepts non-accepting computation histories for that machine. D(P) will accept if and only if there are no accepting computation histories for M on w; this would allow us to decide A_{TM}, which we know to be undecidable.

References

  1. ^ Christine L. Mumford; Lakhmi C. Jain (2009). Computational Intelligence: Collaboration, Fusion and Emergence. Springer. p. 337.  
  2. ^ Andreas Blass (22 October 2010). Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday. Springer. p. 468.  
  3. ^ Lenore Blum (1998). Complexity and real computation. Springer. p. 31.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.