Anything that is algorithmically computable can be computed by a standard 1tape Turing machine.Extensions include:
 multiple tapes, each with its own independent scan head
 twoway infinite tape (with a single scan head)
 a single tape with multiple independent scan heads
 Setup. The guest configuration is converted to a suitable host configuration. For example a multitape configuration must be translated into a single tape configuration. The host machine is augmented by many more states and the alphabet has new specialpurpose symbols.
 Stepbystep simulation. Each single step of the guest machine is effected by multiple steps of the host machine.
 Teardown phase. If the guest machine enters a halt state, the host machine enters the corresponding "prehalt" state and then "tears down" the simulation, leaving a terminal configuration on the host which somehow mirrors the intended terminal configuration on the guest.
K ∪ K×{0,1,2,...}It adds to the guest's state set K, the simulation state set K×{0,1,2,...}.
 The true starting configuration at state s of the guest starting machine is mapped into a suitable host configuration with host state set to [s,0], representing the start state of the "stepbystep" simulation

The intended guest step
δ(s,σ)=(p,X)
runs through one or more (usually more) host states to achieve a simulated outcome:[s,0] ⇾ [s,a1] → [s,a2] ... → [p,0]
 Continue on from the next simulation state group [p,0] → ..., etc.
 If we enter the state [h,0], where h ∈ H then begin the final phase of the simulation.

The state sequence
[h,0] → ... → h
represents the teardown sequence, arriving at the true halt state h.
Multitape TM
Of the three extensions listed above, the multiple tape model yields the most productive mechanism for "extending" TM capabilities. Of course, we're not extending it, just making it vastly easier to compute. A ktape Turing machine M = (K,Σ,δ,s,H) has the same meaning as a regular TM except:δ: (KH) × Σ^{k} → K × (Σ∪{L,R})^{k}The read action which guides the tape is the state plus the contents of each of the scanned positions:
(q, a_{1}, a_{2}, ..., a_{k})At each step, all the scan heads make a step. A scan head can simply write back the symbol that it is reading and thereby act as if nothing happened. A configuration is simply a state, plus the configuration information on each tape:
(q, w_{1}a_{1}u_{1}, w_{2}a_{2}u_{2}, ..., w_{k}a_{k}u_{k})The definition of ⊢ is the same idea applied to multiple tape where
δ(q, a_{1}, a_{2}, ..., a_{k}) = (p, b_{1}, b_{2}, ..., b_{k})with b_{i} ∈ Σ ∪ {L,R}
Computing/Deciding
A multitape TM computes a function f: Σ_{0}* → Σ_{0}* in the sense that the computation starts and ends on tape 1, i.e.(s, #w, #, ..., #) ⊢* (h, #f(w), ?, ..., ?)The ? indicates that we do not care about the final contents of the additional tapes. As before, accepting a language means to compute the decision function: f: Σ_{0}* ⇾ {Y,N}
Machine diagrams
One can attach a superscript to the machines to indicate tapes on which this actions takes place. For example, with a 2tape machine: L^{2}: go left on tape 2
 L^{1,2}: go left simultaneously on both tapes
 a^{1}: write the symbol a on tape 1
 b^{1,2}: write the symbol b simultaneously on both tapes
 L^{1}R^{2}: left on tape 1 and right on tape 2; this is ambiguous because the single action appears as two actions in sequence; fortunately it does not matter.
 L_{#}^{1}: run L_{#} on tape 1
 if tape 1 reads an "a"
 if tape 1 reads "a" and tape 2 reads "#"
if tapes 1 and 2 read "anything but #":
The condition is that "if both tapes are scanning a nonblank symbol."
The target machine N can use u and v
as "parameters" for the actions it takes.
There is no formal syntax, so you can use u != #^{1}
just as well as
u = #^{1}.
The test in the previous condition implicitly uses an "and" of two tests.
You can explicitly use "or" if necessary.
You have to be careful about potential
nondeterminism for conditions with more than one target.
For example, if you have one condition as
a^{1} ("a" on tape 1)
and a second condition, leading to a different
target as
v!=#^{2} (nonblank on tape 2)
both conditions can be true. This could be understood,
however, as a deterministic choice if tape 1 has "precedence over"
tape 2 as in an if (..) else if (..) statement
where both boolean clauses are true.
Examples
Compute f(w) = ww with a 2tape machine. We want (s, #w, #) ⊢* (h, #ww, ?) L = { w ∈ {a,b}* : w = a^{n}b^{n} }
 L = { w ∈ {a,b}* : w = xcx^{R} }
 L = { w ∈ {a,b}* : #a(w) = #b(w) }
 L = { w ∈ {a,b}* : w = w^{R} }
 L = { w ∈ {a,b}* : w = xx^{R} }
 L = { w ∈ {a,b}* : w = a^{n}b^{n}c^{n} }
(s, #w, #) ⊢* (h, #Y, ?) if w ∈ L (s, #w, #) ⊢* (h, #N, ?) if w ∉ L
Equivalence of 1tape and multitape TMs
The goal is to show that you can simulate the steps of an ntape TM by a 1tape TM using an expanded symbol set, expanded state set and a simulation whereby each step of the ntape machine is achieved by multiple steps of the 1tape machine. The textbook sketches this equivalence proof and so do I in the Multitape/Standard Equivalence section below.Other TM extensions
2way infinite tape
Not a really attractive extension, but relatively easy to argue the ability to simulate it by a 1tape TM. I do so in the Twoway infinite tape section below.Multihead TM
A khead TM is one in which there are k marked positions (which can be the same position). A move consists of reading each of the positions and independently doing actions at each position. One has to somehow deal with conflicts if two or more heads mark the same position. It's easy to see that this can be simulated by a ktape TM in which each of the tapes have identical contents.RAM Turing Machines
This is section 4.4. Skip this for now. It's a nontraditional, but interesting alternative TM computational model (yet still equivalent to a standard TM).Nondeterministic TMs
Nondeterminism is addressed in section 4.5 of the textbook. A Nondeterministic Turing Machine (NTM)M = (K,Σ,Δ,s,H)modifies the TM by using a transition relation instead of a function:
Δ ⊆ ((KH) × Σ) × (K × (Σ∪{L,R}))Configurations and the ⊢ relation are defined in the same way, except of course that ⊢ is not a function. What do we do with an NTM? Because of the nondeterminism, there is no predictability about what might happen when it halts; the same input may lead to different halting configurations. A standard TM may "run forever" by never reaching a halt state, however it always "keeps running" by virtue of using a transition function. With a transition relation, the computation may simply stop in a nonhalt state because the relation is undefined for the current state and current symbol. A missing transition can alway be relaced by a "runforever" construction.
Accepting a Language
The easiest thing to do with a NTM is accept a language. The accepting idea is the same as for a standard TM, except that, for the same input string, some computations sequences may halt and others not. An NTM M accepts a string w, if the starting configuration can arrive at a halting configuration by some computation sequence. We can express this as saying that w is accepted if and only if there exists an h ∈ H such that:(s, #w) ⊢* (h, ?)Consequently w ∉ L if no computation sequence leads to a halting configuration. Just like the situation with a regular TM, a language L is the language accepted by an NTM if
 all strings w ∈ L are accepted
 all strings w ∉ L are not accepted, i.e., no computation sequence ever reaches a halt state
Omit nondeterministic decision and computation
Definition 4.5.2 and the subsequent two paragraphs in the textbook discuss the concept of an NTM either deciding a language or computing a function. Both of these notions are quite unintuitive precisely because of the nondeterminism aspect.Please omit this discussion and assume that an NTM can only acceot a language.
Simple Example
Consider the NTMM = ( {s,p,h}, {a,#,>}, Δ, s, {h} )with Δ defined by the diagram:
( s, >aaaa )
The only halting computation sequence is to run right past the a's.
( s, >aaaa )
⊢
( p, >aaaa )
⊢
( p, >aaaa )
⊢
( p, >aaaa# )
⊢
( h, >aaaa# )
Going left is an "inifinite loop" failure:
( s, >aaaa )
⊢
( s, >aaaa )
⊢
( s, >aaaa )
⊢
( s, >aaaa )
⊢
...
This is a "nowhere to go" failure:
( s, >aaaa )
⊢
( p, >aaaa )
⊢
( p, >aaaa )
⊢
( s, >aaa# )
Number Generator
The idea of "guessing a number" plays a big part in nondeterministic computation. As far as Turing Machines go, unary number encoding is the best since there are no concerns for efficiency. This starts with empty tape and writes a unary number, i.e., a string in 1*:
The "guess a number" NTM
For example:
write 0:
( s, ># )
⊢*
( h, >## )
write 2:
( s, ># )
⊢*
( , >#1# )
⊢*
( , >#11# )
⊢*
( h, >11# )
Textbook example
The strategy of nondeterministic usage is usually "guess and check," meaning that we guess the solution nondeterministically and check its validity using a deterministic procedure. The following is example 4.5.1 from the textbook. Let C ⊆ {1}* be the set of unary representations of composite (i.e., nonprime) numbers. We describe an NTM which accepts L. Technically, we haven't discussed multitape NTMs, and so you should think of this solution as: Run the nondeterministic "guessing" on a single tape.
 Expand the single tape to multiple tapes and then do the deterministic "checking" part.
 Start with the input on the tape: #n

Nondeterministically choose two numbers p, q,
both ≥ 2,
and add them to the tape:
#n#p#q#
We need an NTM M which writes at least two 1's onto blank tape to the right of the current tape square. This is done twice after moving past n. What is M?#n
to#n#p#q#

Now run a deterministic TM to compute the product of p and q.
We can do this best with a 4tape TM which effects these steps:
( #n#p#q#, #, #, # ) start ( #n#p#q, #, #, # ) L_{#}L_{#} ( #n#p#q, #p#, #, # ) write p on tape 2 ( #n#p#q#, #p#, #q#, # ) write q on tape 3 ( #n, #p, #q, # ) reset tapes 2 and 3 ( #n, #p#, #q#, #(p*q) ) for each 1 in p, copy q onto tapee 4
We end up with n on tape 1 and p*q on tape 4.  Scan right and compare the ones on tape 1 and tape 4. If we see an equal number, halt, otherwise "run forever" (or provide no way to continue the computation).
{ x ∈ {a,b}* : x = ww where w ∈ {a,b}* }
NTM/TM Equivalence
The textbook proves this theorem:Given an NTM M = (K,Σ,Δ,s,H) which accepts a language L, then there is a TM which accepts the same languageStart from the usual starting configuration with a string on the tape. The idea of the TM simulation is that it runs systematically through all possible computations; if it finds one that halts, then it halts. The method is called a dovetailing procedure. Consider a configuration in the NTM (p, wau). The next configuration in the computation is dictated by the existence of
((p,a), (q,X)) ∈ Δwhere (q,X) ∈ K × (Σ∪{L,R}). And so the number R = K*(Σ+2) represents the maximum number of ways a configuration can branch in a nondeterministic computation. Enumerate the possibile computation steps from a give configuration:
1: (q_{1},X_{1}) 2: (q_{1},X_{2}) ... Σ+2: (q_{1},X_{Σ+2}) Σ+2+1: (q_{2},X_{1}) ... R: (q_{K},X_{Σ+2})The set of all sequences of these computation steps of length n represent all the possible computations of length n that could take place from the starting configuration.
The equivalent TM
Our equivalent TM has 3 tapes:( >#w, >#, ># )The description of these tapes are:
 the input string: this is never changed
 the computation sequence string, dictating a sequence of branching possibilities
 where the computation is carried out
A Simple Examle
Consider the following NTM (different than the one above).( {s,p,h}, {a,b,#,>}, Δ, s, {h} )with Δ defined by the diagram:
(s, >#abbb)Here is a successful sequence and two failure sequences:
(s,R)(p,R)(p,R)(p,R)(p,R)(h,#) a halting sequence (s,R)(p,R)(p,R)(s,b)(s,b) ... an infinite loop (s,R)(p,R)(p,R)(p,a) a nonhalting sequence which stopsFor example, we would apply the first sequence like this:
(s, >#abbb) δ(s,#)=(s,R): (s, >#abbb) δ(s,a)=(p,R): (p, >#abbb) δ(p,b)=(p,R): (p, >#abbb) δ(p,b)=(p,R): (p, >#abbb) δ(p,b)=(p,R): (p, >#abbb#) δ(p,b)=(h,#): (h, >#abbb#)We can encode the computation steps as alphabetic symbols. There are 3 states and 6 tape head behavior possibilites: {a,b,#,>,L,R} requiring 18 symbols:
A = (s,a) G = (p,a) M = (h,a) B = (s,b) H = (p,b) N = (h,b) C = (s,#) I = (p,#) O = (h,#) D = (s,>) J = (p,>) P = (h,>) E = (s,L) K = (p,L) Q = (h,L) F = (s,R) L = (p,R) R = (h,R)So the sequences according to the encodings are these strings:
FLLLLO a halting sequence FLLBBB... an infinite loop FLLG a nonhalting sequence which stopsThe idea is to be able to enumerate all possible computation sequences in {A,B,...,R}* in lengthfirst/lexicographic order:
A,B,...,R, AA,AB,...,AR, BA,BB,...,BR, ..., AAA,...and try each one. Most do not get very far. By virtue of the starting configuration with the tape head reading a blank, any sequence not starting with F cannot go anywhere.
Simulation behavior
Initialize the TM with: tape 1: the marked string to run (e.g., >#abbb)
 tape 2: the initial computation string (e.g., "A")
 tape 3: empty
 Copy the input string on tape 1 onto tape 3.

Run the NTM M on tape 3 according to the steps
dictated by the computation string on tape 2:
c_{1}c_{2}...c_{n} (e.g., FLL from our example)
The possibilities are: Every step c_{i} can be taken and the state after the last step is a halt state. Halt the Simulator.
 Every step can be taken, but the last state is not a halt state. Go to step 3.
 The NTM cannot proceed at step c_{i} (most strings will fall into this category). Go to step 3.

Clear tape 3 and reset it to >#.
This is computable.
If n = length of the computation string on tape 2, then
the tape head can have moved at most n positions right.
Consequently, we are guaranteed that all positions are blank after this many:
max(w, n)
 Run a dedicated TM on tape 2 to produce the next computation string. For example, if the current string is "FLL", then the next one will be "FLM". Go back to step 1.
(#w, #A, #w) ⊢* (#w, #A, ?) (#w, #B, #w) ⊢* (#w, #B, ?) ... (#w, #F, #w) ⊢* (#w, #F#, ?) computation completes, but not in halt state ... (#w, #R, #w) ⊢* (#w, #R, ?) (#w, #AA, #w) ⊢* (#w, #AA, ?) (#w, #AB, #w) ⊢* (#w, #AB, ?) ... (#w, #FLLLO, #w) ⊢* (#w, #FLLLO#, ?) computation completes in halt state
Twoway infinite tape
A twoway infinite tape has no left end and therefore can go left or right an arbitrary amount. We will indicate how such a TM can be simulated by a 2tape TM. Since a 2tape TM can be simulated by a standard TM, we are effectively simulating the 2way TM by a standard TM. A configuration for this machine is again a state and marked string, where the marked string has a minimal number of blanks on either end. Thus...###a####...should be represented simply by a#, not a##, not #a, etc. To make this correspond to a 2tape machine, think of the left end of the starting configuration string as position 0. Tape 1 has all nonnegative positions and tape 2 all negative positions. Thus
(s, ba#ab)
...  #  #  b  a  #  a  b  #  ... 
2  1  0  1  2  3  4  5 
([s,0], >ba#ab, >)From here we start the simulation.
tape 2:  >  #  #  ...  
1  2  
tape 1:  >  b  a  #  a  b  ...  
0  1  2  3  4 
s host starts in guest machine start state ... setup [s,0] = start state for running simulation of first step δ(s,#) = (p,R) ... [p,0] = start state for running simulation of δ(p,_) = (q,_) ... [q,0] = start state for running simulation of δ(q,_) = (h,_) ... [h,0] = start state for teardown phase ... teardown h host halts in guest machine halt state
Simulation steps
Every operation must check which is the "active" tape for every simulation. Start with the symbolwrite operation:δ(p,a) = (q,b), b ∈ ΣA psuedocode version gives us the idea:
// assume you are reading an "a" if (state == p and tape1 == > and tape2 == a): tape2 = b else if (state == p and tape2 == > and tape1 == a): tape1 = b state = qThe relevant TM state diagram portion is also pretty simple, it only takes one step to complete:
δ(p,a) = (q,L)we have to watch out for tape1 reaching the left end:
// assume you are reading an "a" if (state == p and tape1 == > and tape2 == a): go Right on tape2 else if (state == p and tape2 == > and tape1 == a): go Left on tape1 if (tape1 == >): go Right on tape2 state = qThe relevant TM state diagram portion is a bit more complex than the first:
δ(p,a) = (q,R)must watch out for tape2 reaching the left end:
// assume you are reading an "a" if (state == p and tape1 == > and tape2 == a): go Left on tape2 if (tape2 == >): go Right on tape2 else if (state == p and tape2 == > and tape1 == a): go Right on tape1 state = qThe relevant TM state diagram portion is analogous the previous:
(s, ba#ab) Setup: ([s,0], >ba#ab, >) δ(s,#) =(p1,L): ⊢ ([p1,0], >ba#ab, >) δ(p1,a)=(p2,b): ⊢ ([p2,0], >bb#ab, >) δ(p2,b)=(p3,L): ⊢ ([p3,0], >bb#ab, >) δ(p3,b)=(p4,L): ⊢ ([p3,], >bb#ab, >#) ⊢ ([p4,0], >bb#ab, >#) δ(p4,#)=(p5,a): ⊢ ([p5,0], >bb#ab, >a) δ(p5,a)=(p6,L): ⊢ ([p6,0], >bb#ab, >a#)
Shutting down
When the computation is complete, we are obliged to reveal exactly what is the outcome of the computation. This means we need to move the terminal configuration entirely on tape 1, starting from the "0" position. For example, if the computation ends with 2way machine configurationa##abababa#bbbthe string may be distributed anywhere on the 2 tapes, e.g.:
tape 2:  >  b  a  #  #  a  
tape 1:  >  a  b  a  b  a  #  b  b  b 
tape 1:  >  a  #  #  a  b  a  b  a  b  a  #  b  b  b 
a b #We might imagine the following 2to1tape conversion:
 replace the marked position by the relevant marking character and scan to left end on both tapes
 scan to the right end of tape 2, shifting the contents of tape 1 right at each step
 reversecopy tape 2 onto tape 1
 locate the marked character and replace it by its true character
 remove the left end marker on tape 1 to get the outcome
tape 2: >ba##a tape 1: >ababa#bbb a. tape 2: >ba##a tape 1: >ababa#bbb b. tape 2: >ba##a tape 1: >#####ababa#bbb c. tape 2: >ba##a tape 1: >a##abababa#bbb d. tape 2: >ba##a tape 1: >a###abababa#bbb e. tape: a###abababa#bbb
Boundary marker
Implicit in step (b) is that we have know what is the rightmost character on each tape; a blank will not serve as delimiter because they may be embedded within nonblanks. To solve this problem, introduce a special boundary character, B. Make the initial configuration of the twoway machine be:tape 2: >B tape 1: >ba#abBEvery time B is read, the simulator simply moves it right one position as follows:
 move right
 write a B
 move left
 write a blank
 read (a blank)
tape 2: >ba##a####B
tape 1: >ababa#bbb#####B
and so we would want to "trim" both tapes
tape 2: >ba##aB
tape 1: >ababa#bbbB
Now B gives us the right end of each tape and we can complete
the steps with a few modifications.
Multitape/Standard Equivalence
We want to argue that anything that a multitape TM does can be done by a singletape TM. This argument is the subject of Theorem 4.3.1 in the textbook. Theorem: If M = (K,Σ,δ,s,H) is a multitape TM, then there is a standard TM,M′ = (K′,Σ′,δ′,s′,H)which effects the same "halting behavior" as M. Regarding our terminology above, M is the guest machine and M′ the host machine. The guest is started with tape 1 in a standard starting configuration and other tapes empty:
(s, >α, >, ... )The string α is a mixture of "normal" symbols (in Σ_{0}) plus blanks used as argument separators. We want:
 M halts in state h ∈ H if and only if M′ halts in the same state. The two machines share the same halt states and so whatever interpretation we draw from the halt state for M is achieved by M′
 M halts with tape 1 contents >β if and only if M′ halts with the same tape contents.
(s, >α, >, ... ) ⊢* (h, >β, ...) in M
if and only if
(s′, >α) ⊢* (h, >β) in M′
Sample Scenario
Let's imagine the situation for a 2tape guest machine with alphabet {a,b,#,<} with starting configuration:(s, >ab, >)being simulated by a 1tape host machine.
Setup phase
The host machine expresses the starting configuration of the guest machine (2tape TM) with added multitape symbols as follows:[s,0],  >  >  #  #  #  #  ... 
1  0  0  
>  a  b  
1  0  0  
↑ 
[1,>,1,>], [0,a,0,#], [0,b,0,#]These quadruple symbols belong to the finite set
{0,1} × Σ × {0,1} × ΣWe can write the 1tape host machine start state as:
( [s,0], > [1,>,1,>] [0,a,0,#] [0,b,0,#] )The separating blanks in the tape are for visual clarity only.
Simulation Steps
The marked position will be at the left end between phases of the simulation. Suppose the guest machine has this applicable transition:δ(s,>,>) = (q_{1},R,R)Then the simulation achieves this outcome:
( [s,0], > [1,>,1,>] [0,a,0,#] [0,b,0,#] ) ⊢* ( [q_{1},0], > [0,>,0,>] [1,a,1,#] [0,b,0,#] )The 1tape TM must read the symbols, one at a time from both tapes, and enter a state which recognizes:
tape 1 symbol = > and tape 2 symbol = >
From this state, it simulates R^{(1,2)}.
A depiction of the process is this:
The R^{(1,2)} simulation achieves the desired outcome by doing the R operation successively on each track. For example, "go right on track 1" is:
 scan right for [1,x,y,z]
 replace by [0,x,y,z]
 go right
 replace [0,u,v,w] by [1,u,v,w]
 scan left for >
( [q_{1},0], > [0,>,0,>] [1,a,1,#] [0,b,0,#] ) δ(q_{1},a,#) = (q_{2},a,b) ⇒ ( [q_{2},0], > [0,>,0,>] [1,a,1,b] [0,b,0,#] ) δ(q_{2},a,b) = (q_{3},R,R) ⇒ ( [q_{3},0], > [0,>,0,>] [0,a,0,b] [1,b,1,#] ) δ(q_{3},b,#) = (q_{4},b,a) ⇒ ( [q_{4},0], > [0,>,0,>] [0,a,0,b] [1,b,1,a] )Expanding the next step, we indicate some intermediate steps:
δ(q_{4},b,a) = (q_{5},R,L) ⇒ ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [1,b,1,a] # ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] # ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] # ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [0,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,0,a] [1,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,0,b] [0,b,0,a] [1,#,0,#] ) ⊢* ( [q_{4},], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] ) ⊢* ( [q_{4},h], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] ) ⊢ ( [q_{5},0], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] )The first group of substeps illustrate the simulation feature that when the scan head goes right and sees a "#", it must replace it by [0,#,0,#]. In particular, the true blank marks the boundary of the computation.
Shutting down
When the simulation machine enters the state [h,t_{0}], it begins shutting down. We want to discard all the information on tapes other than tape #1 and enter the target halt state. Suppose that we ended with this host configuration:( [h,0], > [0,>,0,>] [0,a,0,b] [1,b,0,a] [0,#,1,#] )
 Scan right up to the real blank boundary, replacing each quadruple
[0,σ,?,?] by σ:
⊢* ( [h,], > [0,>,0,>] a [1,b,0,a] # # )

Shift configuration 1 square left (up to real left end), thereby deleting
the left end quadruple:
⊢* ( [h,], > a [1,b,0,a] # # )

Scan left for the remaining quadruple or real left end. Replace by first tape symbol:
⊢* ( [h,], > a b )
If you reach the left end without finding a quadruple, it means tape 1's left end actually was the selected symbol.  Enter targeted halt state
⊢ (h, >ab)