代写代考 COMP3630/6360: Theory of Computation Semester 1, 2022

COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Turing Machines

This lecture covers Chapter 8 of HMU: Turing Machines
Turing Machine
Extensions of Turing Machines Restrictions of Turing Machines
Additional Reading: Chapter 8 of HMU.

Turing Machine: Informal Definition
Finite Control
ààà ààà
ó An tape extending infinitely in both sides
ó A reading head that can edit tape, move right or left.
ó A finite control.
ó A string is accepted if finite control reaches a final/accepting state

Turing Machine: Formal Definition
A Turing machine M = (Q,Σ,Γ,δ,q0,B,F) comprises of:
ó Q: finite set of states
ó Σ: finite set of input symbols
ó Γ: finite set of tape symbols such that Σ ⊆ Γ
ó δ: transition function. δ is a partial function over Q × Γ, where the first component is viewed as the present state, and the second is viewed as the tape symbol read. If δ(q,X) is defined, then
Tape symbol Next State Reading head direction to move next
Present state
Ü(qà X) = (q0à Yà D) The symbol replacing X
ó B ∈ Γ \ Σ is the blank symbol. All but a finite number of tape symbols are Bs.
ó q0: the initial state of the TM.
ó F: the set of final/accepting states fo the TM.
ó Head always moves to the left or right. Being stationary is not an option. ó The Turing Machine is deterministic.

Describing TMs
ó Turing machines can be defined by describing δ using a transition table.
ó They can also be defined using transition diagrams (with labels appropriately altered)
If Ü(qàX) = (q0àYàD) q
A TM that accepts any binary string that does not contain 111
0=0 ! 1=1 !

Instantaneous Descriptions of TMs
ó An instantaneous description (or configuration) of a TM is a complete description of the system that enables one to determine the trajectory of the TM as it operates.
ó The instantaneous description or configuration or ID of a TM contains 3 parts: (a)
The (finite, non-trivial) portion of tape to the left of the reading head; (b) the state that the TM is presently in; and (c) the (finite, non-trivial) portion of the tape to the right of the reading head.
State, Tape contents, Reading head location
1  i  Ô àààXààà
i D segment to the strict left z
segment from the head onwards
Xi àààXÔ
qààà q à à à
ààà z state X1 àààXi1 q
B B X X X à à à X z 123 ÔB
segment to the strict left
à à à qàààzàààBXXXàààXBBàààz
z i 1 zs t a t e X1àààXÔBq
B à à à head
B 123Ô qBiX1àààXÔ
segment from the head onwards

‘Moves’ of a TM
ó JustasinthecaseofaPDA,weuse⊢toindicateasinglemoveofaTMM,and⊢ MM
to indicate zero or a finite number of moves of a TM.
Present ID X1àààXi1qXi àààXÔ
(1 à i à Ô)
X1 àààXÔBi1q qBi X1 : : : XÔ
Transition
Ü(qàXi)=(q0àYàR) Ü(qà Xi ) = (q0à Yà L)
Next ID X1àààXi1Yq0Xi+1àààXÔ
X1 à à à Xi2q0Xi1Y Xi+1 à à à XÔ
X1 à à à XÔBi1Y q0
X1 àààXÔ1q0XÔY i = 1 X1àààXÔBi2q0BY i1
Y q0X2 à à à XÔ i = 0
Y q0Bi1X1 à à à XÔ i 0 q0BY X2 à à à XÔ i = 0 q0BY Bi1X1 à à à XÔ i 0
Ü(qà B) = (q0à Yà R) 0
Ü(qàB) = (q0àYàR) Ü(qà B) = (q0à Yà L)
Ü(qàB) = (q àYàL)

Language accepted by a TM
ó A string w is in the language accepted by a TM M iff q0w ⊢ αpβ for some p ∈ F. M
ó Another notion of acceptance that is common is to require a TM to halt (i.e., no further transitions are possible).
ó It is always possible to design a TM such that the TM halts when it reaches a final state without changing the language the TM accepts.
ó However, we cannot require (all) TMs to halt for all inputs.
ó A language L is recursively enumerable if it is accepted by some TM.
ó A language L is recursive if it is accepted by a TM that always halts on its input.
Context-free
Recursively Enumerable (RE)

Extensions of TMs
Extensions of TMs

Extensions of TMs
Multiple-Track TMs
Multiple-track TM
ó There are k tracks, each having symbols written on them.
ó The machine can only read symbols from each tape corresponding to one location,
i.e., all symbols in a column at any one time.
ó A k-track TM with tape alphabet Γ has the same langauge-acceptance power as a
TM with tape alphabet Γk .
Finite Control
ààà X1 ààà ààà X2 ààà .
ààà Xk ààà

Extensions of TMs
Multi-tape TMs
Multiple-tape TM
ó There are k tapes, each having symbols written on them.
ó The machine can each tape independently, i.e., the symbols read from each tape need
not correspond to the same location
ó After a read of each tapes, each reading head can move independently to the right, left, or stay stationary.
Finite Control
ààà X1 ààà
ààà X2 ààà .

Extensions of TMs
Multi-tape TMs
Theorem 7.1.1
Every language that is accepted by a multi-tape TM is also recursively enumerable (i.e., accepted by some ‘standard’ TM).
Proof of Theorem 7.1.1
ó Let L be accepted by a k-tape TM M. We’ll devise a 2k-track TM M′ that accepts L.
ó Every even tape of M′ has the same alphabet as that of the k-tape TM. The 2ith
track of M′ contains exactly the same contents as the ith tape of M.
ó Every odd track has an alphabet {B, †, }, and contains a single †. The 2i − 1th track of M′ contains † at the location where the ith reading head of M is located.
Finite Control
6 1214 011001100
M Finite Control 10 11
à à à 0 1 1 0 à à 0à 1 1 0 0 à à à 1 1 1 1 0à à à 0 0 0
11110000 45
ààà ààà101010101 ààà

Extensions of TMs
Multi-tape TMs
Proof of Theorem 7.1.1
ó The state of M′ has 3 components: (a) the state of M; (b) the number of †s to its strict left; and (c) a vector of length k with each component taking value in Γ ∪ {?} .
ó Each move of M takes multiple moves of M′, and is a sweep of the tape from the location of the leftmost † to that of the rightmost † and back performing the changes to tracks that M would do to its corresponding tapes.
ó At the beginning of the sweep, the head of M′ is at a location where the leftmost † is and the state of M′ is (q, 0, [?, · · · , ?]). The head moves to the right uncovering †s and the corresponding track symbols (are stored in the third component of the state).
ó The right sweep ends when the second component is k.
à à à 1 1 1 1 0à à à 0 0 0 11110000 1
M0 Finite Control 011001100
M Finite Control
à à à 0 1 1 0 à à 0à 1 1 0 0 1
State: (q0 à 0à [0à 1à 1])
ààà ààà101010101 ààà

Extensions of TMs
Multi-tape TMs
Proof of Theorem 7.1.1
ó At this stage, M′ knows the input symbols M will have read, and knows what actions to take.
ó It then sweeps left making appropriate changes to the tracks (just like M does to its tape) each time a † is encountered. M′ also moves the †s accordingly.
ó The left sweep ends when the second component is zero. At this time, M′ would have completed moving the †s and the track contents; they’ll now match those of M.
ó M′ then moves the state to (q′,0,[?,··· ,?]) and start the next sweep if q′ is not a final state.
ó Note that M′ mimics M and hence the languages accepted are identical.

Extensions of TMs
Multi-tape TMs
ó The running time of a TM M with input w is the number of moves M makes before it halts. (If it does not, the running time is ∞).
ó The time complexity TM : {0,1,…} → {0,1,…} of a TM M is defined as follows: ó TM (n) := maximum running time of M for an input w of length n symbols.
Theorem 7.1.2
The time taken for M′ in Theorem 7.1.2 to process n moves of M is O(n2).
Outline of Proof of Theorem 7.1.2
ó After n moves of M, any two heads of M can be at most 2n locations apart.
ó Each sweep then requires 4n moves of M′.
ó Each track update requires a finite number of
moves. Totally, to update the tracks, Θ(k) n time steps are needed.
Moves of M
Location of tape heads

Extensions of TMs
Non-deterministic TMs
Non-deterministic TM: δ(q,X) is a set of triples representing possible moves. Theorem 7.1.3
For every non-deterministic TM M, there is a TM N such that L(M) = L(N).
Outline of Proof of Theorem 7.1.3
(N does Breadth-First exploration of IDs of M)
ID2à1 ID2à2 à à à ID2àk
(If M does not halt at ID1)
(If M does not halt at ID1 and ID2à1)
(If M does not halt at ID1, ID2à1 and ID2à2)
ID1 ID2à1 ID2à2 à à à ID2àk
I D3à3 I D3à4
ID1 ID2à1 ID2à2 à à à ID2àk ID3à1 ID3à2
ID1 ID2à1 ID2à2 à à à ID2àk ID3à1 ID3à2 ID3à3 ID3à4

Extensions of TMs
Outline of Proof of Theorem 7.1.3
ó We can devise a 2-tape TM M that simulates N.
ó M first replaces the content of the first tape by ‡ followed by the ID that N is initially in, which is then followed by a special symbol †, which serves as ID separator. (M uses the second tape as scratch tape to enable this operation).
ó If the ID corresponds to a final state, N halts (as would M).
ó If not, M then identifies all possible choices for the next IDs for N and enters each one of them followed by † at the right end of it’s first tape. (Again, M uses the second tape as scratch tape to enable this operation)
ó M then searches for † to the right of ‡, changes the † to a ‡ (to signify that it is processing the succeeding ID), and processes that ID in the similar way.
ó M haltsatanIDiffM wouldatthatID.

Restrictions of TMs
Restrictions of TMs

Restrictions of TMs
TM Semi-infinite Tape
Theorem 7.2.1
Every recursively enumerable language is also accepted by a TM with semi-infinite tape.
Outline of Proof of Theorem 7.2.1
ó Given a TM M that accepts a language L, construct a two-track TM M′ as follows.
ó The first and second tracks of M′ are the R and L semi-infinite parts of the tape of M.
ó First, write a special symbol, say † at the leftmost part of the second track; this indicates to M′ that a left move is not to be attempted at this location.
ó At any time, M′ keeps track of whether M is to the right or left of its start location.
ó If M is to the strict right of its start location, M′ mimics M on the first track. If M is to the strict left of its start location, M′ mimics M on second track, but with the head directions reversed. M′ detects the start by the † symbol.
ó It can be formally shown that M′ accepts a string iff M accepts it.
M L$R L$R ààà ààà ààà 210 1 2 ààà
M0 012àààL$R ààà
12 ààà R$L

Restrictions of TMs
Multi-stack Machines
A multistack machne is a PDA with several independent stacks (i.e., one can be popping a symbol, while the other is writing a symbol).
Theorem 7.2.2
Every recursively enumerable language is accepted by a two-stack PDA
Outline of Proof of Theorem 7.2.2
TM PDA PDA
BbaaB baa baa
Finite Control b a
Finite Control
Finite Control
Finite Control
R semi-infinite portion of TM’s tape Strict L semi-infinite portion of TM’s tape
ó † indicates the end of the stack content (to prevent PDA from halting)
ó If TM moves right changing tape symbol X to Y and state from q to q′, PDA moves from state q to q′ popping X from left stack and pushing Y to the right stack.

Restrictions of TMs
Counter Machines
ó A counter machine is a multi-stack machine whose stack alphabet contains two symbols: Z0 (stack end marker) and X
ó Z0 is initially in the stack.
ó Z0 maybereplacedbyXiZ0 forsomei≥0
ó X maybereplacedbyXi forsomei≥0.
ó A counter machine effectively stores a non-negative number.
Finite Control
XX XX XX Z0 X

Restrictions of TMs
Counter Machines
Theorem 7.2.3
Every recursively enumerable language is accepted by a three-counter machine
Outline of Proof of Theorem 7.2.3
ó We know a two-stack PDA can simulate any TM.
ó We’ll show that a 3-counter machine can simulate any (two stack) PDA.
ó WLOG,letthestackalphabetofΓ={0,1,…,r−1}.
ó Suppose the first stack contains Y1(top), . . . , Yk . Then the first counter stores Y1 + rY2 + · · · + rk−1Yk . Similarly for the second stack.
ó The third counter is used to change the two stack contents.
ó Popping the top symbol a stack (say A) = finding quotient when Y1+rY2+···+rk−1Yk isdividedbyr.
ó pop r X’s from stack A, and push a single X on the third stack. Repeat until all Xs are exhausted on the stack where popping is performed.
ó Now empty stack A and copy the third stack contents onto stack A.
ó Change Y1 to some Y1′ requires adding or subtracting, which is done by popping or pushing the corresponding number of Xs.

Restrictions of TMs
Counter Machines
Outline of Proof of Theorem 7.2.3
ó pushing a symbol Z onto a stack (say A) = compute rC + Z where C is the number presently stored in the stack A.
ó pop one X from stack A, and push r Xs on the third stack.
ó Finally push Z Xs onto the third stack. Now empty stack A and copy the third
stack contents onto stack A.
ó Since the above three are the only operations needed to simulate a TM on a two-stack PDA, we can stimulate a 2-stack PDA and hence a TM using a 3-counter machine.
Theorem 7.2.4
Every recursively enumerable language is accepted by a two-counter machine
Outline of Proof of Theorem 7.2.4
ó The key idea: simulate three counters using one, and use the other for manipulations.
ó The first counter stores 2i 3j 5k where i , j , k are the contents of the 3-counter machine.
ó Updates to the stack involve: (a) divide by 2,3, or 5; (b) multiply by 2,3, or 5; or (c) identify if i or j or k is zero (check divisibility).
ó Each operation can be easily seen to be done with a spare counter.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts