Turing Expressions

[Mark Hopkins]

This article is a continuation of the series:

The Spinor Representation of Formal Languages
The Formal Language Representation of Algebras
The Equational Representation of Formal Languages
Context Free Expressions
The Algebraic Representation of Formal Languages
The Hardest Context Free Language

in which the correspondence between automata and systems of equations
developed in the third article will be applied to arrive at a type of formal
expression, analogous to regular expressions, for representing all recursively
defined languages. They will be called Turing expressions.

The notation is not just analogous to that used for regular expressions,
Turing expressions *are* regular expressions. What's different is that the
algebra underlying the expressions is non-trivial. This was also the case
with the notation developed for context free expressions, in which case the
algebra was denoted as the Context Free Algebra. Here, it will be called the
Turing Algebra.

A Turing machine is traditionally thought of as an abstract machine with a
finite state control and a tape which is infinitely extensible in one or both
directions.

Somewhere along the tape is the machine's "read-head". In going from
instant to instant, the current machine state and the contents of the tape
under the read-head will determine a series of actions consisting of possibly
writing something to the tape under the read-head, which may then be moved one
space to the left or right.

One way to think of a Turing Machine is as a 2-stack machine with the
following configuration:

(Left Stack) Read-Head (Right Stack)

with the tops of the two stacks being next to one another and the read-head
considered as being over the top of the right stack (if it's non-empty).

A move left consists of popping an item off the left stack and pushing it
on the right-stack. If the tape is extensible toward the left and the left
stack happened to be empty, then the move left would consist only of pushing a
blank symbol on the right stack. A move toward the right is defined
analogously.

The read operation consists of popping a value off the right stack (or
testing for the right stack being empty) and then possibly pushing it back.
The write operation consists of replacing the top of the right stack by the
value written or if the right stack was empty, pushing the value written on
it.

There are several definitions of a Turing Machine in the literature
depending on which set of operations are treated as being primitive. The set
I prefer to work with here will consist of the following primitives:

Wab: Read the current symbol. If it's a, then write
symbol b and move right.
La: Read the current symbol. If it's a, then move left.

If a, b and x denote stack symbols, s and t denote sequences of stack symbols,
B the blank symbol and q, and q' the current and following states in the
finite state control, then these operations can be depicted as follows:

Wab: s qa t |- s bq' t
Wab: q(s, ta) |- q'(sb, t)
WBb: q(s, 1) |- q'(sb, 1)
La: q(sx, ta) |- q'(s, tax)
LB: q(sx, 1) |- q'(s, x) x not equal to B.
q(sB, 1) |- q'(s, 1)

In the finite state control there will be one state, s, called the
start state and one state, f, called the final state. The initial state of
the Turing Machine will be considered to be s(1, w') where w' is the reverse
of the initial word on the tape. If the final state is reached, f(s, t),
then the input word is considered to be accepted. Alternatively, if one is
defining a Turing Transducer then when the final state f(s, t) is reached
the output st' will result where t' is the reverse of the word t.

Recalling the definition of the Infinite State Automaton from
the article "The Equational Representation of Formal Languages":

Infinite State Automaton:
* Q: A set of states, possibly infinite.
* X: An input alphabet.
* D: The state transition relation, a subset of
(Q x (X union {1}) x Q
* F: A set of final states, a subset of Q.
* s: The start state, an element of Q.

a Turing Machine may be regarded as a special case of an infinite state
automaton with the following restrictions:

* Q = Q0 x S* x S*, Q0 a finite set,
S = { 1, 2, ..., s } = stack alphabet

An element (q, s, t) of Q0 x S* x S* will be denoted
q(s, t) for consistency with the discussion above.

* X is empty.
* F = { f(s, t): s and t are in S* }
* D is a subset of Q-{f} x {1} x Q, and transitions are restricted
to the following forms:
q(s, ta) |- q'(sb, t)
q(s, 1) |- q'(sb, 1)
q(sx, ta) |- q'(s, tax)
q(sx, 1) |- q'(s, x) x not equal to B.
q(sB, 1) |- q'(s, 1)
* If
q(s, ta) |- q'(sb, t)

is a transition in D then so are:

q(s', t'a) |- q'(s'b, t')

for all stack words s' and t'. Similar requirements of
symmetry are placed on the other 4 types of transitions.

The symmetry requirement is what makes the state transition relation
finitely presentable.

Analogous to the previous discussion on Context Free Expressions,
the following state operators may be defined:

un: q(w, t) |--> q(w n, t)
vn: q(w n, t) |--> q(w, t)
q(w n', t) |--> 0 if n, n' distinct
q(1, t) |--> 0
p0: q(1, t) |--> q(1, t)
q(w n, t) |--> 0
and
Un: q(s, w) |--> q(s, w n)
Vn: q(s, w n) |--> q(s, w)
q(s, w n') |--> 0 if n, n' distinct
q(s, 1) |--> 0
P0: q(s, 1) |--> q(s, 1)
q(s, w n) |--> 0

with each of the algebras { un, vn, p0 } and { Un, Vn, P0 } being
instances of the Context Free Algebra described therein, and with the
commutation relations

xy = yx x = un, vn, p0; y = Un, Vn, P0

In terms of these, the operations Wab, La may be written as follows:

Wab: q(s, ta) |--> q(sb, t) b not equal to B.
q(s, tx) |--> 0 x not equal to a.
Thus Wab = Va ub = ub Va

WBb: q(s, tB) |--> q(sb, t)
q(s, 1) |--> q(sb, 1)
q(s, tx) |--> 0 x not equal to B.
Thus wBb = VB ub + P0 ub = (VB + P0) ub = ub (VB + P0)

La: q(sx, ta) |--> q(s, tax) a not equal to B.
q(sx, tb) |--> 0 b not equal to a.
Thus La = L (Va Ua)
where L = sum (vx Ux: x in S)

LB: q(sx, tB) |--> q(s, tBx)
q(sx, tb) |--> 0 b not rqual to B.
q(sx, 1) |--> q(s, x) x not equal to B.
q(sB, 1) |--> q(s, 1)
Thus LB = L (VB UB) + L' P0 + vB P0
where L' = sum (vx Ux: x in S - {B})
and thus L = L' + vB UB.

The last operator may be rewritten in the following form:

LB = L (VB UB) + L' P0 + vB P0
= L' (VB UB) + vB UB VB UB + L' P0 + vB P0
= L' VB UB + vB UB + L' P0 + vB P0
= L' (VB UB + P0) + vB (UB + P0)

This leads to the following operator set:

Wab = Va ub = ub Va
wBb = VB ub + P0 ub = (VB + P0) ub = ub (VB + P0)
La = L (Va Ua)
LB = L' (VB UB + P0) + vB (UB + P0)
where L' = sum (vx Ux: x in S - {B})
and L = L' + vB UB.


Applying the correspondence between infinite state automata and
systems of equations (in "The Equational Representation of Formal
Languages"), we may regard each state as being an expression for
which an equation of the following form is stated:

q = \q + union (x q': q x |- q') + union (q': q |- q')

where x is in the set X. Since X is empty, the only final states
are those of the form f(s, t) and no transitions are allowed from these
states, then the equations take on the simpler form:

q(s, t) = union (q'(s', t'): q(s, t) |- q'(s', t'))
if q is in Q - {f}.

f(s, t) = 1

Every term on the right hand side of the first set of equations may be written
in the form:
q'(s', t') = A q'(s, t)
where
A is in { Wab: a, b in S } union { La: a in S }

the second set of equation may also rewritten in linear form so that only
one equation has 1 on the right hand side:

f(sx, t) = f(s, tx) = L f(sx, t)
f(1, tx) = f(1, t) = p0 Vx f(1, tx)
f(1, 1) = 1

For a Turing Transducer, the second equation can be modified to the form:

f(1, tx) = x f(1, t) = x p0 Vx f(1, tx)

Since p0 Vx f(1, 1) = p0 0 = 0, then the last two equations may be
generalised to the form:

f(1, t) = \f(1, t) + p0 Vx f(1, t)
where
\f(1, t) = 1 if t = 1
= 0 else

Similarly, since
p0 Vx f(sx, t) = Vx p0 f(sx, t) = Vx 0 = 0
and L f(1, t) = sum (vx Ux f(1, t))
= sum (Ux vx f(1, t)) = 0

then all three equations may be combined in the form:

f(s, t) = \f(s, t) + (p0 Vx + L) f(s, t)
where \f(s, t) = 1 if s = t = 1
= 0 else

This leads to a modified system of equations of the form:

q(s, t) = sum (A q'(s, t), over all transitions q(s,t) |- q'(s',t'))
and f(s, t) = \f(s, t) + (p0 Y + L) f(s, t)
where Y = sum (Vx: x in S)

Each state may be represented as an infinite column vector whose
first element is the (1, 1) component:

q = (q(1, 1), ...)'

(where R' denotes the transpose of the row vector R). Then the system
of equations will reduce to a finite set of right-linear equations of the
form:
q = sum (A q')
f = |0> + (p0 Y + L) f
where Y = sum (Vx: x in S)
<0| = (1 0 0 0 ...)
|0> = <0|', the transpose of <0|

For a Turing Transducer, the second equation will take the same form, but Y
will be modified to read:

where Y = sum (x Vx: x in S)

Thus every state will be expressible in the form:

q = RE (p0 Y + L)* |0>
= RE L* p0 Y* |0>

where RE is a regular expression over the set { Wab, La }.

Since the initial state, given an input word w in S*, is

s(1, w') = <0| U(w) s

where the notation is being used:

U(w a) = U(w) Ua, if w is in S*, a in S
U(1) = 1

Thus, the Turing computation on an input word, w, can be expressed in the
form:
s(1, w') = <0| U(w) RE L* p0 Y* |0> (1)

where RE is the regular expression associated with state s.

Every recursively defined language over S can be expressed in the form
(1), where Y denotes the operator

Y = sum (x Vx: x in S)

associated with the Turing Transducer. This is true because for such a
language, L = { w0, w1, w2, ... } recognized by a Turing machine T, there will
be a Turing transduction T' that will generate the set as follows:

s(1, c b^n a) |- ... |- f(1, wn') = wn
where a, b, c are auxillary symbols not in the set S.

In particular, T' may be defined roughly as follows:

Assumed: all the words over the alphabet, S, can be enumerated
counting from 1.
Input a b^n c:
C := 0;
while there are b's between a and c:
C := C + 1;
run the Turing machine T on word number C in the set X*;
if T accepts word number C, then erase one of the b's.
end while
return word number C

If L only has m words in it, then the process will go into an infinite
computation on any input a b^n c for n > m, so will not be represented
by any finite word over the algebra associated with the Turing transducer
T'. So regardless of whether L is finite or infinite, we may write the
language as the regular expression

L = sum (1, c b^n a): n >= 0)
= <0| Ua (sum Ub^n: n >= 0) Uc RE L* p0 Y* |0>
= <0| Ua Ub* Uc RE L* p0 Y* |0>

Thus we arrive at the

Fundamental Theorem of Turing Expressions
Every recursively defined language can be expressed in the form

L = <0| R |0>

where R is a regular expression over the product of two
Context Free Algebras with generators { p0, un, vn } and
{ P0, Un, Vn}, satisfying the relations:

<0| un = 0 = vn |0>
<0| p0 = <0|, |0> = p0 |0>

vn un' = 1 if n = n'
= 0 otherwise
p0 un = 0 = vn p0
p0^2 = p0

p0 + u1 v1 + ... + us vs = 1

analogous relations for { P0, Un, Vn }, and where the sets

S, { p0, un, vn }, and { P0, Un, Vn }

are mutually commuting.

Therefore, R will be called a Turing expression. The associated algebra
will be called the Turing Algebra.

Analogous to what was done in the article on Context Free Expressions, this
algebra may be realised as the product of two quotient tensor spaces
V*/R x W*/R' over two (s+1)-dimensional modules V and W (s = the size of the
stack alphabet S), by the correspondence:

<0| <--> <0| <0|'
|0> <--> |0> |0>'
un <--> |n>
vn <--> <n|
p0 <--> |0><0|
Un <--> |n>'
Vn <--> <n|'
P0 <--> |0>'<0|'

where <n|, |n> denote the basis elements of V, and <n|', |n>' the basis
elements of W. The quotient is taken with respect to the set of relations:

<n| |n'> = 1 if n = n', 0 otherwise (R)
|0><0| + |1><1| + ... + |s><s| = 1

over V, with an analogous set (R') over W. And so every Turing expression
will be a regular expression over the algebra:

S* x Turing Algebra
= S* x (V*/R) x (W*/R')