TM Extensions

Extensions of the TM model include a variety of ways to potentially enhance the computing power of a standard TM. The goal, in all cases, is to show that these extensions provide no additional computing power because their behavior can effectively be simulated by a standard TM, thus giving credence to the Church-Turing Thesis:
Anything that is algorithmically computable can be computed by a standard 1-tape Turing machine.
Extensions include: We can think of such a simulation as we would think of a virtual machine, so call the simulator the host machine (for example, the standard TM) and the machine being simulated the guest machine (for example, the multi-tape TM).
  1. Setup. The guest configuration is converted to a suitable host configuration. For example a multi-tape configuration must be translated into a single tape configuration. The host machine is augmented by many more states and the alphabet has new special-purpose symbols.
  2. Step-by-step simulation. Each single step of the guest machine is effected by multiple steps of the host machine.
  3. Tear-down phase. If the guest machine enters a halt state, the host machine enters the corresponding "pre-halt" state and then "tears down" the simulation, leaving a terminal configuration on the host which somehow mirrors the intended terminal configuration on the guest.
The host machine's state set is something like this:
K  ∪  K×{0,1,2,...}
It adds to the guest's state set K, the simulation state set K×{0,1,2,...}.

Multi-tape 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 k-tape Turing machine M = (K,Σ,δ,s,H) has the same meaning as a regular TM except:
δ: (K-H) × Σ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, a1, a2, ..., ak)
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, w1a1u1, w2a2u2, ..., wkakuk) 
The definition of is the same idea applied to multiple tape where
δ(q, a1, a2, ..., ak) = (p, b1, b2, ..., bk)
with bi ∈ Σ ∪ {L,R}

Computing/Deciding

A multi-tape 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 2-tape machine: Although L#1,2, per se, doesn't make sense, it can be thought of as the sequence of two machines L#1 and L#2 in any order.

Decisions can also be done with a tape-number superscript: This notation has obvious limitations. One of the key points is that when the tape symbol can be more than one possibility, we want to express the symbol as a parameter. One possible expansion is this:
if tapes 1 and 2 read "anything but #":
The condition is that "if both tapes are scanning a non-blank 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 non-determinism for conditions with more than one target. For example, if you have one condition as a1 ("a" on tape 1) and a second condition, leading to a different target as v!=#2 (non-blank 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 2-tape machine.

We want (s, #w, #) ⊢* (h, #ww, ?)
Having more than 1 tape makes everything much easier. For example, a DCFL can always be decided with 2 tapes using the second tape as a stack. Here are some other standard examples: In each case you want to compute
(s, #w, #) ⊢* (h, #Y, ?)   if w ∈ L
(s, #w, #) ⊢* (h, #N, ?)   if w ∉ L

Equivalence of 1-tape and multi-tape TMs

The goal is to show that you can simulate the steps of an n-tape TM by a 1-tape TM using an expanded symbol set, expanded state set and a simulation whereby each step of the n-tape machine is achieved by multiple steps of the 1-tape machine.

The textbook sketches this equivalence proof and so do I in the Multi-tape/Standard Equivalence section below.

Other TM extensions

2-way infinite tape

Not a really attractive extension, but relatively easy to argue the ability to simulate it by a 1-tape TM. I do so in the Two-way infinite tape section below.

Multi-head TM

A k-head 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 k-tape 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 non-traditional, but interesting alternative TM computational model (yet still equivalent to a standard TM).

Non-deterministic TMs

Non-determinism is addressed in section 4.5 of the textbook. A Non-deterministic Turing Machine (NTM)
M = (K,Σ,Δ,s,H)
modifies the TM by using a transition relation instead of a function:
Δ ⊆ ((K-H) × Σ)  ×  (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 non-determinism, 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 non-halt state because the relation is undefined for the current state and current symbol. A missing transition can alway be relaced by a "run-forever" 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

Non-deterministic decision and computation

Definition 4.5.2 and the subsequent paragraph in the textbook discuss the concept of an NTM either deciding a language or computing a function. Both of these notions are quite unintuitive and so for simplicity we will omit this part.

Non-deterministic computation, although not practical, plays a big role in Computer Science Theory. The famous class NP is the set of all decision problems (in the theory, languages) which can be accepted by a certain NTM in polynomial time.

The strategy of non-deterministic computation is usually "guess and check," meaning we guess the solution and check its validity, the computation time revolves around the checking aspect. The non-determinism means that we are able to "guess correctly" and thereby solve the problem. Alternatively, you can think of non-determinism as being able to generate and test all possible solutions simultaneously.

Simple Example

Consider the NTM M = ({s,p,h}, {a,#,>}, σ, {h}):
Both states s and p give non-deterministic choices for behavior on reading an a symbol. Suppose we started with this initial configuration:
( 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 does 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 non-deterministic 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 following is example 4.5.1 from the textbook. Let C ⊆ {1}* be the set of unary representations of composite (i.e., non-prime) numbers. We describe an NTM which accepts L.

Technically, we haven't discussed multi-tape NTMs, and so you should think of this solution as: You'll see that the non-deterministic part is often pretty trivial. Here it just means "guess two numbers ≥ 2."
  1. Start with the input on the tape: #n
  2. Non-deterministically 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?
    And so the machine R#MM takes
    #n
    to
    #n#p#q#
  3. Now run a deterministic TM to compute the product of p and q. We can do this best with a 4-tape 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.
  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).

We could convert this into a "brute force" deterministic model by systematically generating all pairs of numbers and then running the second part, but the non-deterministic version has obvious simplicity.

Non-determinism trivializes many computational problems. Try showing the following language is accepted by an NTM with 3 tapes:
{ 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 language
Start 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 non-deterministic computation. Enumerate the possibile computation steps from a give configuration:
1:       (q1,X1)
2:       (q1,X2)
...
|Σ|+2:   (q1,X|Σ|+2)
|Σ|+2+1: (q2,X1)
...
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:
  1. the input string: this is never changed
  2. the computation sequence string, dictating a sequence of branching possibilities
  3. 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:
It accepts the language ab*, but can make "mistakes" based on the 3 possible transitions at state p. Suppose the initial configuration is:
(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 non-halting sequence which stops
For 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 non-halting sequence which stops
The idea is to be able to enumerate all possible computation sequences in {A,B,...,R}* in length-first/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: The execution goes like this:
  1. Copy the input string on tape 1 onto tape 3.
  2. Run the NTM M on tape 3 according to the configuration steps dictated by the computation string on tape 2:
    c1c2...cn    (e.g.,  FLL from our example)
    
    The possibilities are:
    • Every step ci 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 ci (most strings will fall into this category). Go to step 3.
  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)
    
  4. 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.
If the NTM never reaches a halt state, the TM simulator will run forever, but if some computation sequence can reach a halt state, the TM simlator will find it. Referring to our example, the simulation with w = abbb proceeds as follows:
(#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

Two-way infinite tape

A two-way 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 2-tape TM. Since a 2-tape TM can be simulated by a standard TM, we are effectively simulating the 2-way 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 2-tape machine, think of the left end of the starting configuration string as position 0. Tape 1 has all non-negative positions and tape 2 all negative positions. Thus
(s, ba#ab)
... # # b a # a b # ...
  -2 -1 0 1 2 3 4 5  
is transformed via the setup phase to the 2-tape starting configuration
([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
The idea is that the tape with left end marker unselected holds the position where the two-way infinite tape head should reside. The 2-tape simulating machine always maintains exactly one left end marker selected indicating the "idle" tape.

We discussed above that the simulation is best understood by think of the host machine (i.e. the simulator) states as state pairs which maintain the guest state (that of the machine being simulated) as the first component while the second component goes through a sequence of simulation states:
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 tear-down phase
...      tear-down
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 symbol-write operation:
δ(p,a) = (q,b),  b ∈ Σ
A psuedo-code 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 = q
The relevant TM state diagram portion is also pretty simple, it only takes one step to complete:
The operations which move either left or right have the opposite sense if the active position is on tape 2, e.g., move left means move toward the negative direction, meaning "move right" on tape 2. The other issue is that after moving, if left end markers are read on both tapes, it means you need to switch the active tape and move the opposite way on the other tape. So for
δ(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 = q
The relevant TM state diagram portion is a bit more complex than the first:
The intermediate state, [p,1], serves to do the current tape switch if necessary. The operation
δ(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 = q
The relevant TM state diagram portion is analogous the previous:
Both [p,1] and [p,2] may be necessary for different symbols. The move left/right simulation gives us a good idea of the usage of intermediate states.

Let's imagine a sample run:
(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 2-way machine configuration
a##abababa#bbb
the 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
In this case we need to convert to this before actually halting:
tape 1:  > a # # a b a b a b a # b b b

We need to take the 2-tape machine out of its simulation mode to do so, abandoning the marked positions on the tapes. To do so we introduce marking characters, one for each regular character (except left end):
a  b  #
We might imagine the following 2-to-1-tape conversion: Here is a depiction of the shutdown:
   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 non-blanks. To solve this problem, introduce a special boundary character, B. Make the initial configuration of the two-way machine be:
tape 2: >B
tape 1: >ba#abB
Every time B is read, the simulator simply moves it right one position as follows: The B effectively acts like a blank, but it marks the furthest point that tape head ever reached. After step (a) the tapes contents may actually be this:
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.

Multi-tape/Standard Equivalence

We want to argue that anything that a multi-tape TM does can be done by a single-tape TM. This argument is the subject of Theorem 4.3.1 in the textbook.

Theorem: If M = (K,Σ,δ,s,H) is a multi-tape 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:
  1. 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′
  2. M halts with tape 1 contents >β if and only if M′ halts with the same tape contents.
Expressed notationally,
(s, >α, >, ... ) ⊢* (h, >β, ...)   in M
if and only if
(s′, >α) ⊢* (h, >β)                in M′

Sample Scenario

Let's imagine the situation for a 2-tape guest machine with alphabet {a,b,#,<} with starting configuration:
(s, >ab, >)
being simulated by a 1-tape host machine.

Setup phase

The host machine expresses the starting configuration of the guest machine (2-tape TM) with added multi-tape symbols as follows:
[s,t0], > >####...
100
>ab
100
The new symbols are "quadruples" consisting of regular tape symbols plus position marker symbols {0,1}. Tape 1 is on the bottom, so read the symbols from bottom to top:
[1,>,1,>], [0,a,0,#], [0,b,0,#]
These quadruple symbols belong to the finite set
{0,1} × Σ × {0,1} × Σ
We can write the 1-tape 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,>,>) = (q1,R,R)
Then the simulation achieves this outcome:
( [s,0],  > [1,>,1,>] [0,a,0,#] [0,b,0,#] )   ⊢*

                      ( [q1,0], > [0,>,0,>] [1,a,1,#] [0,b,0,#] )
The 1-tape 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:
Assuming that Σ = {#,>,a,b}, the outcome of scanning the first tape scan can be one of 4 possibilities, and we end up in one four states before the second tape scan. The second tape scan branches to another 4 states. So we are describing 16 possible states to reach before doing the associated action. This scenario occurs for every non-halt state. Efficiency is not a concern!

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: Taking the next 3 steps, we get these simulated outcomes for the applicable transitions:
                       ( [q1,0], > [0,>,0,>] [1,a,1,#] [0,b,0,#] )

δ(q1,a,#) = (q2,a,b) ⇒ ( [q2,0], > [0,>,0,>] [1,a,1,b] [0,b,0,#] )

δ(q2,a,b) = (q3,R,R) ⇒ ( [q3,0], > [0,>,0,>] [0,a,0,b] [1,b,1,#] )

δ(q3,b,#) = (q4,b,a) ⇒ ( [q4,0], > [0,>,0,>] [0,a,0,b] [1,b,1,a] )
Expanding the next step, we indicate some intermediate steps:
δ(q4,b,a) = (q5,R,L) ⇒ 

                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [1,b,1,a] # )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] # )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] # )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [0,#,0,#] )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] )

                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,1,a] [1,#,0,#] )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,0,a] [1,#,0,#] )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,0,b] [0,b,0,a] [1,#,0,#] )
                  ⊢* ( [q4,-], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] )
                  ⊢* ( [q4,h], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] )
                     
                  ⊢ ( [q5,0], > [0,>,0,>] [0,a,1,b] [0,b,0,a] [1,#,0,#] )
The first group of sub-steps 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,t0], 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,#] )
  1. Scan right up to the real blank boundary, replacing each quadruple [0,σ,?,?] by σ:
    ⊢* ( [h,-], > [0,>,0,>] a [1,b,0,a] # # )
    
  2. Shift configuration 1 square left (up to real left end), thereby deleting the left end quadruple:
    ⊢* ( [h,-], > a [1,b,0,a] # # )
    
  3. 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.
  4. Enter targeted halt state
    ⊢ (h, >ab)
    


© Robert M. Kline