形式语言与自动机_笔记整理(三)_图灵机与递归语言、递归可枚举语言
Turing Machines
Turing-Machine Theory
- The purpose of the theory of Turing machines is to prove that certain specific languages have no algorithm.
- Start with a language about Turing machines themselves.
- Reductions are used to prove more common questions undecidable.
Picture of a Turing Machine
Turing-Machine Formalism
A TM is described by:
- A finite set of states (Q, typically).
- An input alphabet (Σ, typically).
- A transition function (δ, typically).
- Takes two arguments:
- A state, in Q.
- A tape symbol in Γ.
- δ(q, Z) is either undefined or a triple of the form (p, Y, D).
- p is a state.
- Y is the new tape symbol.
- D is a direction, L or R.
- Takes two arguments:
- A start state (
q0 , in Q, typically). - All tape except for the input is blank initially.
- A set of final states (F ⊆ Q, typically).
Instantaneous Descriptions of a Turing Machine
- Initially, a TM has a tape consisting of a string of input symbols surrounded by an infinity of blanks in both directions.
- The TM is in the start state, and the head is at the leftmost input symbol.
- An ID is a string
αqβ , whereαβ includes the tape between the leftmost and rightmost nonblanks. - The state
q is immediately to the left of the tape symbol scanned. - If
q is at the right end, it is scanningB .- If
q is scanning a B at the left end, then consecutiveB 's at and to the right ofq are part ofα .
- If
- As for PDA's we may use symbols ⊦ and ⊦* to represent "becomes in one move" and "becomes in zero or more moves" respectively, on ID'*s.
Formal Definition of Moves
- If δ(q, Z) = (p, Y, R), then
-
αqZβ⊦αYpβ - If Z is the blank B, then also
αq⊦αYp
-
- If δ(q, Z) = (p, Y, L), then
- For any X,
αXqZβ⊦αpXYβ - In addition,
qZβ⊦pBYβ
- For any X,
Languages of a TM
A TM defines a language by final state, as usual.
L(M) = {w |q0w⊦∗I , where I is an ID with a final state}.Or, a TM can accept a language by halting.
H(M) = {w |q0w⊦∗I , and there is no move possible from ID I}.
Equivalence of Accepting and Halting
- If L = L(M), then there is a TM M'such that L = H(M').
- If L = H(M), then there is a TM M" such that L = L(M").
Proof of 1: Final State -> Halting
- Modify
M to becomeM′ as follows:- For each final state of
M , remove any moves, soM′ halts in that state. - Avoid having
M′ accidentally halt.- Introduce a new state
s , which runs to the right forever, e.i.,δ(s,X)=(s,X,R) for all symbolsX . - If
q is not a final state, andδ(q,X) is undefined, letδ(q,X)=(s,X,R) .
- Introduce a new state
- For each final state of
Proof of 2: Halting -> Final State
- Modify
M to becomeM" as follows:- Introduce a new state
f , the only final state ofM" . -
f has no moves. - If
δ(q,X) is undefined for any stateq and symbolX , define it byδ(q,X)=(f,X,R) .
- Introduce a new state
Recursively Enumerable Languages
The classes of languages defined by TM's using final state and halting are called the recursively enumerable languages.
Recursive Languages
An algorithm is a TM, accepting by final state, that is guaranteed to halt whether or not it accepts.
If
Every CFL is a recursive language.
Turing Machine Programming
Example 1
Construct a DTM to accept the language
Example 2
Program a DTM to shift its input words right by one cell, placing a blank in the leftmost cell.
Example 3
Program a DTM to shift its input word cyclically to the right by one position.
Example 4
Let = {a, b} and L = {
More About Turing Machines
Programming Tricks
Multiple Tracks
- Think of tape symbols as vectors with k components, each chosen from a finite alphabet.
- Makes the tape appear to have k tracks.
- Let input symbols be blank in all but one track.
Marking
A common use for an extra track is to mark certain positions.
Almost all tape squares hold B (blank) in this track, but several hold special symbols (marks) that allow the TM to find particular places on the tape.
Caching in the State
The state can also be a vector.
First component is the control state.
Other components hold data from a finite alphabet.
Turing Machine with Storage
Example: Using These Tricks
- This TM doesn't do anything terribly useful; it copies its input w infinitely.
- Control states:
- q: Mark your position and remember the input symbol seen.
- p: Run right, remembering the symbol and looking for a blank. Deposit symbol.
- r: Run left, looking for the mark.
- States have the form [x, Y], where x is q, p, or r and Y is 0, 1, or B.
Only p uses 0 and 1. - Tape symbols have the form [U, V].
- U is either X (the mark) or B.
- V is 0, 1 (the input symbols) or B.
- [B, B] is the TM blank; [B, 0] and [B, 1] are the inputs.
- The Transition Function
- Convention: a and b each stand for either 0 or 1.
-
δ([q, B], [B, a]) = ([p, a], [X, a], R).
In state q, copy the input symbol under the head (i.e., a ) into the state.
Mark the position read.
Go to state p and move right. -
δ([p, a], [B, b]) = ([p, a], [B, b], R).
In state p, search right, looking for a blank symbol (not just B in the mark track). -
δ([p, a], [B, B]) = ([r, B], [B, a], L).
- When you find a
B , replace it by the symbola carried in the cache. - Go to state
r and move left.
- When you find a
-
δ([r,B], [B,a]) = ([r,B], [B,a], L).
In state r, move left, looking for the mark. -
δ([r,B], [X,a]) = ([q,B], [B,a], R).
When the mark is found, go to stateq and move right.
But remove the mark from where it was.q will place a new mark and the cycle repeats.
Semi-infinite Tape
- We can assume the TM never moves left from the initial position of the head.
- Let this position be 0; positions to the right are 1, 2, … and positions to the left are –1, –2, …
- New TM has two tracks.
- Top holds positions 0, 1, 2, …
- Bottom holds a marker, positions –1, –2, …
Restrictions
- Two stacks can simulate one tape.
- One holds positions to the left of the head; the other holds positions to the right.
- In fact, by a clever construction, the two stacks to be counters = only two stack symbols, one of which can only appear at the bottom.
Extensions
- More general than the standard TM.
- But still only able to define the same languages.
- Multitape TM.
- Nondeterministic TM.
- Store for name-value pairs.
Multitape Turing Machines
- Allow a TM to have k tapes for any fixed k.
- Move of the TM depends on the state and the symbols under the head for each tape.
- In one move, the TM can
- change state,
- write symbols under each head,
- and move each head independently.
Simulating k Tapes by One
- Use 2k tracks.
- Each tape of the k-tape machine is represented by a track.
- The head position for each track is represented by a mark on an additional track.
Nondeterministic TM
- Allow the TM to have a choice of move at each step.
- Each choice is a state-symbol-direction triple, as for the deterministic TM.
- The TM accepts its input if any sequence of choices leads to an accepting state.
Simulating a NTM by a DTM
- The DTM maintains on its tape a queue of ID's of the NTM.
- A second track is used to mark certain positions:
- A mark for the ID at the head of the queue.
- A mark to help copy the ID at the head and make a one-move change.
Operation of the Simulating DTM
- The DTM finds the ID at the current front of the queue.
- It looks for the state in that ID so it can determine the moves permitted from that ID.
- If there are m possible moves, it creates m new ID's, one for each move, at the rear of the queue.
- The m new ID's are created one at a time.
- After all are created, the marker for the front of the queue is moved one ID toward the rear of the queue.
- However, if a created ID has an accepting state, the DTM instead accepts and halts.
Store for name-value pairs
- The TM uses one of several tapes to hold an arbitrarily large sequence of name-value pairs in the format
#name*value#…
- Mark, using a second track, the left end of the sequence.
- A second tape can hold a name whose value we want to look up.
Lookup
- Starting at the left end of the store, compare the lookup name with each name in the store.
- When we find a match, take what follows between the * and the next # as the value.
Insertion
- Suppose we want to insert name-value pair
(n,v)
, or replace the current value associated with namen
byv
. - Perform lookup for name
n
. - If not found, add
n*v#
at the end of the store. - If we find
#n*v'#
, we need to replacev'
byv
.- If
v
is shorter thanv'
, you can leave blanks to fill out the replacement. - But if
v
is longer thanv'
, you need to make room.- Use a third tape to copy everything from the first tape to the right of
v'
. - Mark the position of the
*
to the left ofv'
before you do. - On the first tape, write
v
just to the left of that star. - Copy from the third tape to the first, leaving enough room for
v
.
- Use a third tape to copy everything from the first tape to the right of
- If
Closure Properties of Recursive and RE Languages
- Both closed under union, concatenation, star, reversal, intersection, inverse homomorphism.
- Recursive closed under difference, complementation.
- RE closed under homomorphism.
Union
- Let
L1 =L(M1) andL2=L(M2) . - Assume
M1 andM2 are single-semi-infinite-tape TM's. - Construct 2-tape TM
M to copy its input onto the second tape and simulate the two TM's M1 and M2 each on one of the two tapes, in parallel.
Recursive languages
If
RE languages
accept if either accepts, but you may find both TM's run forever without halting or accepting.
Intersection
-
Recursive languages
-
RE languages
Difference, Complement
Recursive languages
both TM's will eventually halt.
Accept if
Recursive languages are closed under complementation.
RE Languages
can't do it.
Concatenation
RE Languages
- Let
L1=L(M1) andL2=L(M2) . - Assume
M1 andM2 are single-semi-infinite-tape TM's. - Construct 2-tape Nondeterministic TM
M :- Guess a break in input
w=xy . - Move
y to second tape. - Simulate
M1 onx ,M2 ony . - Accept if both accept.
- Guess a break in input
Recursive languages
- Let
L1=L(M1) andL2=L(M2) .
Star
- Same ideas work for each case.
RE Languages
- Guess many breaks, accept if
ML accepts each piece.
Recursive languages
- Systematically try all ways to break input into some number of pieces.
Reversal
- Start by reversing the input.
Then simulate TM for
L to acceptw if and onlywR is inL .Works for Recursive or RE.
Inverse Homomorphism
- Apply
h to inputw . - Simulate TM for
L onh(w) . Accept
w iffh(w) is inL .Works for Recursive or RE.
Homomorphism
- Let
L=L(M1) . - Design NTM
M to take inputw and guess anx such thath(x)=w . M accepts wheneverM1 acceptsx .Note: won't work for Recursive languages.