Reading
Sections 4.1 of Theory of Computing, A Gentle Introduction.
Homework
Check on the homework.

Languages and Turing machines
Your homework from the previous class gave you two ideas of how a Turing machine can be thought of as accepting languages. Halting with something on the tape that indicated accept versus reject, or halting for accepting and failing to halt for reject.

  1. If, for any input string over some alphabet Σ, a Turing machine halts the machine is said to decide a language, specifically the language of all string over Σ for which the machine halts with the tape head pointing to a non-blank cell. Note: The machine tells you when a string is in the language and it tells you when it isn't.

  2. A Turing machine is said to semi-decide the language L of all strings over its input alphabet Σ for which the machine halts. Note: the machine tells you (by halting) when a string is in the language L, but it doesn't give any answer at all for strings not in the language L.

The interesting thing about semi-deciding languages is that the machine answers "yes", but never answers "no". If you're sitting around waiting for the machine, you don't know if the reason it hasn't yet halted is that the input is not in the language, or that it simply needs more time.

Semi-decision might not seem very useful, but the issue isn't really one of utility. Some problems in life are only semi-decidable. For example: Are there other forms of intelligent life in the universe? This question can be answered in the affirmative (if we ever run across another intelligent lifeform), but never in the negative. True, we haven't found another intelligent lifeform yet, but maybe we will tomorrow! So semi-decision is a fact of life. The question is, are there languages that are semi-decidable for Turing machines but not decidable for Turing machines.

Formal Definition of a Turing Machine
Now that we are familiar with Turing machines and decidablilty and semi-decidability on an informal level, it's time to come up with a formal definition for Turing machine. Unfortunately, there are all sorts of models out there for Turing machines. For example, JFLAP thinks a Turing machine has a 2-way infinite tape - the book thinks a Turing machine has a 1-way infinite tape. The book thinks Turing machines may move at a given step or write, but not both - JFLAP thinks Turing machines do both at every step. JFLAP thinks a Turing machine may have several halt states - the book thinks each Turing machine has exactly one halt state. JFLAP thinks the Turing machine's tape is empty except for the input string - the book thinks the first cell of the tape always has a special character in it. And so on.

The conventions we will use for our Turing machine sort of split the difference between the two. They are:

With these conventions out of the way, we are ready to give a formal definition of a Turing machine. Note that h will refer to the halt state, and □ will represent a blank.

A Turing Machine is a 5-tuple (Q,Σ,Γ,δ,s) where
  • Q is the set of states, h ∉ Q, and Q must be finite
  • Σ is the input alphabet
  • Γ is the alphabet of symbols that may appear on the tape at any point in the computation, exluding the blank character □ (note that Σ ⊆ Γ)
  • δ is the transition function
    δ: Q×(Γ∪{□}) → (Q∪{h})×((Γ∪{□})×{L,R,S}
  • s is the start state, s ∈ Q

Thoughts:

Examples
We went over several examples translating diagrams to 5-tuples.
Example 1: with input alphabet {a}.
Example 2: with input alphabet {a,b}.

Mystery Algorithm
Input: DFA M = (Q,Σ,δ,s,W)
Output: TM M' such that ______________________
M' = (Q,Σ,Σ,δ',s), where
δ'(q,x) = {
(h,□,S) if x = □ and q ∈ W
(q,□,S) if x = □ and q ∉ W
(δ(q,x),□,R) if x ≠ □

We followed the mystery algorithm through with input machine M being our favorite DFA, the one that accepts all even length strings of a's and b's. What we discovered is that we got a TM M' that semi-decides the language of all even length strings of a's and b's. In general, given any DFA M, the algorithm produces a Turing Machine that semi-decides L(M). This leads us to the following theorem:

Theorem: Any regular language can be semi-decided by a Turing Machine.


Christopher W Brown
Last modified: Wed Nov 18 14:03:43 EST 2009