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.
-
If, for every input string over some alphabet Σ,
Turing machine $T$ halts,
the machine $T$ is said to
decide a language over Σ — specifically the language of
all string over Σ for which the machine halts with
the tape head pointing to a non-blank cell.
Note: In this case machine $T$ tells you
when a string is in the language and it tells you when it
isn't.
-
A Turing machine $T$ is said to semi-decide
the language L of all strings over its input
alphabet Σ for which the machine halts.
Note: In this case machine $T$ 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:
- a 1-way infinite tape, with no special marker in the first
cell,
- at each step the machine both writes and moves - moves
being L, R and S, and
- exactly one halt state.
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:
- Since Σ and Γ are said to be "alphabets", we
know they are finite.
- Why is the first argument to δ an element of Q rather
than Q ∪ {h}? Because by its very nature
there shouldn't be transitions out of the halt state!
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.
