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,v1,v2...vk) if d = R and v = v1v2...vk
(p,uy,□,λ) if d = R and v = λ
(p,u1...um-1,um,yv) if d = L and u = u1u2...um, where m > 0
Oh yeah, q can't be h, the halt state!

Notice 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)
where x ≠ □ if w ∈ L and x = □ otherwise.

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)
if and only if w ∈ L. In other words, for input not in L the computation never reaches the halt state. For input in L, the computation halts.

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