**Reading**-
Sections 4.1 of
*Theory of Computing, A Gentle Introduction*. **Homework**- Printout the homework and answer the questions on that paper.

**Defining***Configuration*for Turing Machines-
By this point, hopefully, you understand that the tuple from
last class tells us what a TM
*is*, but not how it*works*. It's like having the Monopoly board, pieces and money without having the rules. Of course we already have a good intuitive notion of how TMs work, but how will we make that intuitive notion formal? As with FAs and PDAs, the key is the concept of*configuration*.A configuration should tell us everything we need to know to resume a TM computation from some arbitrary point ... wherever the machine was in its computation when we took a lunch break, perhaps. Hopefully it's clear that what would need to be remembered is the machine's state, what's on the tape, and where the tape head is pointing. This leads us to the following definition:

A

*configuration*of a Turing Machine*M = (Q,Σ,Γ,δ,s)*is a 4-tuple (q,u,x,v) ∈ (Q ∪ {h}) x (Γ ∪ { })* x (Γ ∪ { }) x (Γ ∪ { })* where*q*is the current state,*u*is the string of all characters to the left of the tape head,*x*is the symbol in the cell pointed to by the tape head, and*v*is the string of all symbols to the right of the tape head up to and including the symbol in the last non-blank cell (note that*v*is the empty string if every cell to the right of the tape head is blank).

So, if we consider the machine

... we can write down the computation of the machine on input*abb*as the following sequence of configurations:(q0,λ,a,bb) ⇒ (q1,a,b,b) ⇒ (q0,ab,b,λ) ⇒ (q1,abb, ,λ) ⇒ (h,abb, ,λ)

**Defining***Yields in One Step*, a.k.a. "⇒"-
It should be clear that one configuration yields another by
following the transition function. After all, these machines
are deterministic.
Indeed, in our above example we've already written it down
with our usual symbol for "yields in one step", the ⇒.
However, we need to define this formally for Turing Machines:
For Turing Machine M = (Q,Σ,Γ,δ,s) configuration (q,u,x,v)

*yields*(q',u',x',v')*in one step*if, letting δ(q,x) = (p,y,d):(q',u',x',v') = { (p,u,y,v) if d = S (p,uy,v _{1},v_{2}...v_{k}) if d = R and v = v_{1}v_{2}...v_{k}(p,uy, ,λ) if d = R and v = λ (p,u _{1}...u_{m-1},u_{m},yv) if d = L and u = u_{1}u_{2}...u_{m}, where m > 0Notice that we have to take care not to allow a left move when the tape head is in the first cell. Now we are able to say precisely which sequence of configurations are encountered when a particular Turing machine is given a particular string as input.

**Defining***Decide*and*Semi-Decide*-
Now we are in a position to give technical definitions of our
two concepts of Turing machines defining languages:
*deciding*and*semi-deciding*. (Recall that the halt state is always denoted by*h*!)**Definition:**A Turing machine*M*= (Q,Σ,Γ,δ,s)*decides*the language L ⊆ Σ* if for any string w ∈ Σ* there is a finite sequence of configurations C1,C2,...,Cm such that either- w = λ and (s,λ, ,λ) = C1 ⇒ C2 ⇒ ... ⇒ Cm = (h,u,x,v), or
- w = w1w2...wk, where the wi's are in Σ, and (s,λ,w1,w2...wk) = C1 ⇒ C2 ⇒ ... ⇒ Cm = (h,u,x,v)

Notice that this definition requires that the machine actually halts for any input string in Σ*. So a Turing Machine that

*decides*a language always gives an answer, yes or no, in finite time. The situation isn't so pretty with semi-deciding, of course.**Definition:**A Turing machine*M*= (Q,Σ,Γ,δ,s)*semi-decides*the language L ⊆ Σ* if for any string w ∈ Σ* there is a finite sequence of configurations C1,C2,...,Cm such that either- w = λ and (s,λ, ,λ) = C1 ⇒ C2 ⇒ ... ⇒ Cm = (h,u,x,v), or
- w = w1w2...wk, where the wi's are in Σ, and (s,λ,w1,w2...wk) = C1 ⇒ C2 ⇒ ... ⇒ Cm = (h,u,x,v)

**A note regarding different models of TMs**-
If we decided that we'd rather have our model of a TM use a
2-way infinite tape rather than a 1-way infinite tape, what
would change? The 5-tuple defining a machine would stay
exactly the same. It's the rules governing the mathine's
operation that would have to change. In other words,
*configuration*and*yields-in-one-step*would change. In particular, the last line of the description of what q', u', x' and v' can be in order for (q,u,x,v) ⇒ (q',u',x',v') to hold would have to change to allow moves to the left when u = λ.

Christopher W Brown Last modified: Mon Nov 26 17:16:25 EST 2007