 the tape is semiinfinite and the machine can pass back and forth across the input
 the tape can be written onto
ChurchTuring Thesis
With a PDA, the single stack also becomes a limitation, and we could imagine more powerful models with multiple stacks, etc. In contrast, we will see that the Turing machine represents a maximal model of computation in the sense that anything that can be decided algorithmically, can be done some with a single TM (albeit very complicated).The argument that we're alluding to is called the ChurchTuring Thesis: anything that is algorithmically computable can be computed by a Turing machine. One refers to this as a thesis because there is no effective definition of what algorithmically computable really means. The point is that every effort to extend the TM to a more powerful computational mechanism fails in the sense that any such new mechanism can be modeled by a TM.
Turing Machine Definition
A Turing machine M = (K,Σ,δ,s,H):K = finite set of states Σ = tape alphabet containing special symbols > (left end) and # (blank) s ∈ K is the start state δ: (KH)×Σ → K×(Σ∪{L,R})Further qualifications are that the directional symbols L (go left) and R (go right) do not belong to Σ, and that δ has certain fixed behaviors with respect to the left end symbol:
 if δ(q,>) = (p,X), then X = R or X = >, i.e., when the machine is at the left end, it can only rewrite the left end or go right
 if δ(q,σ) = (p,σ′) where σ ≠ >, then σ′ cannot be >, i.e., we can never write the left end marker except at the left end
 δ(q,σ) = (p,L): change to state p and move the read/write head one symbol left
 δ(q,σ) = (p,R): change to state p and move the read/write head one symbol right
 δ(q,σ) = (p,σ′): change to state p, write a symbol σ′ at the current position and not move the read/write head
Behavior of the left end marker
The TM restrictions (A) and (B) above imply that the left end marker is what it purports to be, a symbol which resides on the left end exclusively throughout the computation and steers the computation away from "falling off the left." Not all TM models are defined in this way. In particular some models allow a TM to run off the left end, in which case it is said that the TM "hangs". Such behavior is considered effectively equivalent to running forever.Halting states
Halting states have some of the connotation of final states in our other machines, except that the definition of δ excludes any further steps once a halting state is reached, and so the machine stops. The point is that, unlike our other machines, the goal is not to consume the input by passing lefttoright over it. In fact, computations can go back and forth across the input multiple times. Therefore, to have some sense of being "done" we need a stronger notion of final state, thus the necessity of halting state. In fact, we can really assume that there is only ever one halt state, h, i.e., H = {h}. In theory, some information might be expressed by the state in which the TM halts; however, in reality, all we ever care about is whether it halts or not, and if it does halt, we can look at the tape contents, not the halt state.Starting point
Every TM starts with a finite portion of the tape replaced by input tape symbols. Usually the interpretation is that we have one or more nonblank strings separated by blanks, like this:>aaa#aaa#####…Unlike PDAs and DFAs, we do not necessarily assume that the read/write head be at a specific position. The idea is that we want to describe TMs by "hooking them together", i.e., one starts where the previous one left off.
Examples: 4.1.1, 4.1.2
As you'll soon see, it is barely worth the effort to work up a graphical depiction of TM behavior, because we develop a whole new system of combining TMs.4.1.1
This is how we could depict example 4.1.1:4.1.2
Configurations
A TM configuration for M = (K,Σ,δ,s,H) belongs toK × >Σ* × (Σ*(Σ{#})∪{ε})The interpretation of a configuration is this:
( state,
tape to (including) the r/w head,
tape after r/w head before infinite blank sequence )
Notational Convention
In order to avoid writing the tape as two strings, it is easier to write a single string and mark the position of the r/w head. The textbook does this by underlining the symbol at the r/w head position, e.g.,(q_{0}, >, aaa ) ⇒ (q_{0}, >aaa) (q, >aa#, bb) ⇒ (q, >aa#bb)A blank can always be within the string, but it can never be at the end of the string unless it is selected. Other textbooks use an even more compact notation whereby we get one string in Σ*KΣ* like this:
(q_{0}, >, aaa ) ⇒ >q_{0}aaa (q, >aa#, bb) ⇒ >aa#qbbHowever, we'll stick with the former version used by this textbook.
The ⊢ relation
As can be expected, we want to define a computation as a series of related configurations obtained by the δ function. Consider our previous examples. In 4.1.1, we made the configuration transformations:(q_{0},>aa) ⊢ (q_{0},>aa) ⊢ (q_{1},>#a)) ⊢ (q_{0},>#a) ⊢ (q_{1},>##) ⊢ (q_{0},>###) ⊢ (h,>###)To define this relation formally, it gets a bit messy with all cases to consider. We want to consider the possible transformations on a given configuration:
(q,wau)
We are assuming:
 if w ≠ ε then w starts with >
 if w = ε, then a = >
 u does not end with #.

δ(q,a) = (p,b).
If w = ε, then a = >, and so the
restrictions on δ dictate that b = >.
Either way
(q,wau) ⊢ (p,wbu)

δ(q,a) = (p,R) and u = ε.
(q,wa) ⊢ (p,wa#)

δ(q,a) = (p,R) and u = σv:
(q,waσv) ⊢ (p,waσv)

δ(q,a) = (p,L). The restrictions on δ dictate that w ≠ ε, so write
w = xσ
(q,xσau) ⊢ (p,xσau)
Combining TMs
We want to create a language and graphical structure for combining TMs.Conditional continuation
The graphical representation is like this:(K_{1}∪K_{2},Σ,δ,s_{1},H_{2})These are the transitions
δ(q,σ) = δ_{1}(q,σ), q ∈ K_{1}H_{1} δ(q,σ) = δ_{2}(q,σ), q ∈ K_{2}H_{2} δ(h,a) = (s_{2},a), h ∈ H_{1} δ(h,σ) = (h_{2},σ), σ ≠ a, h ∈ H_{1}, h_{2} ∈ H_{2}In English,
 run M_{1} until it halts (if it halts)
 if the r/w head is reading the symbol a, leave read head alone and go to state s_{2} in M_{2}
 if the r/w head is reading any other symbol, go to some halt state in M_{2}
Unconditional continuation
Graphically we would write:M_{1} M_{2}It means that, if M_{1} halts, keep R/W head where it is and go to the start state in M_{2}
Inverted conditional continuation
Graphically we would write:Component machines
The machines we use in these compositions are very simple: the σwriting machine: write a symbol σ (subject to TM restrictions about left end) and halt
 the L headmoving machine: go left (subject to TM restrictions about left end) and halt
 the R headmoving machine: go right and halt
Σ = { a, b, #, > }then these component machines would look like this:
 the awriting machine: (a could be #)
a, a b, a #, a >, >
 the L machine:
a, L b, L #, L >, >

the R machine:
a, R b, R #, R >, R
Noop machine
We also have a generic "noop" machine depicted as with only a halt state which is the start state, and no transitions:({h},Σ,∅,h,{h})The noop machine simply serves as a good "place marker" with no actions, for example, acting as a decision point:
Unconditional continuation
Unconditional continuations of these machines can be written simply as juxtapositions:R → R = RR R → # = R#Although the textbook promotes notation like R^{2} being equivalent to RR, it causes inconsistencies when trying to write multitape Turing machines in which the superscript represents the tape number.
Scanning machines
Our input strings to TMs are strings of Σ{#,>} symbols. Blank symbols are used to delineate string input as well as to mark positions which have been read and processed within an input string. Important operations are these:
go left from current head position
until a blank symbol is found 
go right from current head position
until a blank symbol is found 
go left from current head position
until a nonblank symbol is found 
go right from current head position
until a nonblank symbol is found
More advanced machines
Our input strings are always assumed to be composed of the tape symbols excluding blanks and the left end symbol.4.1.8
A copy machine, C, takes an initial tape configuration:#w#and modifies it to
#w#w#We really want the outcome to be "position independent" on the tape, i.e., if the initial tape is this:
>x#w#
where x ∈ (Σ{>})*,
then the outcome is this:
>x#w#w#
Here is copy machine, C:
#R_{#}R_{#}σL_{#}L_{#}σIn reality, there is a separate loop for each σ. For example, if a and b are the two "regular" alphabetic symbols, then the single loop is actually two loops joined at the "R" which is the base of the loop:
#ab#  
L_{#}R  ⇒  #ab 
# R_{#} R_{#}  ⇒  ##b## 
a  ⇒  ##b#a 
L_{#} L_{#} a  ⇒  #ab#a 
R  ⇒  #ab#a 
# R_{#} R_{#}  ⇒  #a##a# 
b  ⇒  #a##ab 
L_{#} L_{#} b  ⇒  #ab#ab 
R  ⇒  #ab#ab 
R_{#}  ⇒  #ab#ab# 
Shift Left machine
A shiftleft machine, S_{L}, takes an initial tape configuration:#w#and modifies it to
w#Again, the result is position independent, i.e., the initial tape is:
>x#w#
where x ∈ (Σ{>})*, and the outcome is this:
>xw#
The machine is:
#abc#  
L_{#}R  ⇒  #abc 
LaRR  ⇒  aabc 
LbRR  ⇒  abbc 
LcRR  ⇒  abcc# 
L#  ⇒  abc# 
Compute the w^{2} function
We'll see what we mean by computing a function in the next section, but the machine:R_{#} → C → S_{L} → L_{#}computes the function
f(w) = wwin the sense that it takes an initial tape configuration:
>#w
to the halting configuration:
>#ww