Seonglae ChoProgramming Technique for TMs
All by these do not improve computation power but these tricks make easy programming
- Storage in the state
We just think of the state as a tuple—No extension to the TM model
The machine remembers the first symbol read in its state
- Multiple tracks just useful structure
- Multiple tape (n-TM or
math: M_n)
Can Use States to remember
Computation power of Convention TM is not different but number of state Big-O is different
Subroutines - Convention TM
Convenient to think of TMs as a collection of interacting components or “subroutines”; M1 calls M2 by passing control to the start state of M2.
General Subroutines
Before returning read the return address into finite control, and transfer back to the right state; may have to erase things on the tape.
Simulating M_n with M
Configurations M2
Simulating Transition M2
Claim: We can simulate a k-tape TM using a single-tape TM M.
proof :
Deterministic: At each step, there is one possible next state, symbols to be written and direction to move the head, or the TM may halt.
Nondeterministic: At each step, there are finitely many possibilities. 1. δ : Q×Γ → 2(Q×Γ×{L,R}). For instance, δ(q,X) = {(p1,Y1,D1),...,(pk,Yk,Dk)} 2.
defined like for deterministic TM. X1X2···Xi−1qXi···Xn X1X2···pXi−1Y ···Xn, if (p,Y,L) ∈ δ(q,Xi); case for right moves is analogous 3. Nondeterministic TM accepts w iff there is a sequence of moves leading to an accepting state, i.e., q0w `∗ αqβ, where q is a final stateClaim: If L is accepted by an NTM N, then there is a DTM M such that L = L(M).
proof:
Note: Clearly, the converse of the above result holds since DTMs are “special forms” of NTMs.
Rough Idea for proof: M tries to keep track of all possible “configurations” that N could possibly be in at any time.
- Works for regular languages because we only need to keep track of the states of the NFA, which is a finite set
- Does not work for PDAs, because we need to keep track of the various possible stack contents
- Is not convenient for TMs either because each choice leads to various possible tape contents, head positions, etc M simulates each possible sequence of computation steps that N may try!
empty completeness?