This definition is slightly different from the traditional one given in
Hopcroft and Ullman, given next.
, where Q is a finite
set of states, S is a finite input alphabet, G (which contains S and has
B, the blank tape symbol, as an element) is a finite tape alphabet,
q0 in Q is the distinguished start state
and F contained in Q is the set of accepting (final) states.
The transition function,
takes the TM from a current (state, tape cell contents) pair to a new
state, new cell contents and head move (left or right).
The TM has accepts its input by making a move into a state of F, and
it is assumed that there are no moves from any state of F.
As a comment, the restriction to only left and right moves is not
difficult to overcome (i.e., adding the S move is easy by increasing Q),
and since there should be no moves from F, it is reasonable to make F
a singleton set and exclude it from consideration in the transition
function as Martin has done.
Not including the blank symbol seem mainly to be done for convenience
when talking about the size of G, since the blank is always included in G.
Definition - Turing Machine configuration (Martin)
A TM configuration is a marked pair, (q, u_a_v), where q is in Q, u and v
are in (G U B)*, and a is in (G U B). Two configurations are equivalent if
they only differ in trailing blanks on v; uav includes all the non-blank
symbols on the tape, and the infinite string of blanks to the right of uav
on the tape is understood to exist without writing it. The _a_ indicates
that the TM's tape head is positioned on the cell containing the symbol a.
Definition - Turing Machine Instantaneous Description (ID) (H&U)
An ID is denoted by alpha_1.q.alpha_2, where alpha_1.alpha_2 is the
string in G* that is the current tape contents, the TM is in state q,
and the head is scanning the cell containing the first symbol of alpha_2.
The dot is used here as the concatenation operator.
As a comment, the ID format used by H&U is easier to write quickly and
is suggestive of the machine itself, although they have to make the
proviso that Q ^ G = 0 in order to avoid ambiguity.
On the other hand, the configuration format used by Martin is easier to
extend to multi-tape TMs, multi-head TMs, and the like.
Definition - Move of a Turing Machine (Martin)
Given TM M = , a move of M is defined by
- (q, ua_b_cv) |- (p, u'_s_v')
where d(q,b) = (p,b',D), and u', s, and v' depend on b' and D:
- D = L : u' = u, s = a, v' = b'cv
- D = S : u' = ua, s = b', v' = cv
- D = R : u' = uab', s = c, v' = v
Definition - Move of a Turing Machine (H&U)
- alpha_1.a.q.b.alpha_2 |- beta_1.p.beta_2
where d(q,b) = (p,b',D), and beta_1 and beta_2 depend on b' and D:
- D = L : beta_1 = alpha_1, beta_2 = a.b'.alpha_2
- D = R : beta_1 = alpha_1.a.b', beta_2 = alpha_2
In both cases, |-* is the reflexive, transitive closure of |- (pronounced
turnstile).
Definition - Language accepted by a Turing Machine (Martin)
Given TM M = , L(M) is defined by
- L(M) = { x in S* | (q0, _B_x) |-* (h, y_a_z) for some y, z in G*, a in G U {B}}
In other words, the TM starts with its head on the leftmost cell of the tape,
which holds a blank, the input occupies the tape immediately to the right of
the first cell, the TM performs some computations on the input and ends up
in the final state.
The initial blank appears to be used by Martin as a convenience for
handling subroutines.
Definition - Language accepted by a Turing Machine (H&U)
- L(M) = { x in S* | q0.x) |-* alpha_1.q.alpha_2 for some alpha_1, alpha_2 in G* and q in F}
This document is
copyright 1995
by Richard E. Newman-Wolfe.
Send comments to nemo@cis.ufl.edu