ELIZA is Turing Complete
by Anthony Hay and Peter Millican (Professor of Philosophy, Hertford College, University of Oxford)
Last updated 2022-11-16; Originally published 2022-11-12
ELIZA is Turing complete. In other words, any possible Turing machine program can be implemented by a suitable ELIZA script conforming to the specification given by Joseph Weizenbaum in his famous paper of 1966.
Finiteness and Termination
This does not, of course, mean that every possible Turing machine program could in practice have been executed on Weizenbaum’s software and hardware in 1966, for both would have had finite capacity (whereas a Turing machine tape is potentially of infinite length). But the syntax of his ELIZA rule-set involves no relevant restriction – for example, there is no specified limit on list size – and hence enables the expression of textual transformations that are sufficient to replicate the abstract processing of any arbitrary Turing machine. So any (terminating) Turing machine program can be executed by an ELIZA script consisting of such transformations, if run on software that faithfully implements Weizenbaum’s specification, and on hardware of sufficient capacity.
The parenthetical restriction above, to terminating Turing machine programs, does not reflect any limitation of ELIZA. For example, the computing machines in Turing’s original 1936 article were designed to write potentially infinite sequences of binary digits onto a tape, going on and on without ever stopping. Clearly this would be beyond the practical representational capacity of any physical hardware, no matter how the Turing machine was implemented. [Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society 42 (1936-37), pp. 230-65. The entire original paper is reproduced with excellent commentary in Charles Petzold’s The Annotated Turing (Wiley, 2008).]
The Significance of Turing Completeness
Turing completeness is significant because it appears that any effectively calculable function can be computed by some Turing machine. This is known as the Church-Turing Thesis, for which Turing gave powerful arguments in §9 and §10 of his classic 1936 paper which introduced his “computing machines”, though it is not strictly provable because of the vagueness of “effectively calculable”. On this basis, the fact that ELIZA can implement any Turing machine implies that an ELIZA script can, in principle, be created to calculate anything that we know how to calculate!
Amongst these possibilities, an ELIZA script can be created to implement a “Universal Turing Machine” (as introduced in §6 of the 1936 paper), which can itself execute any Turing machine program (after the desired program has been suitably encoded and given as input to the ELIZA script). This is not of any serious practical use, since it would be hugely inefficient! But it is theoretically interesting that ELIZA, as defined by Weizenbaum, has such computational power in principle.
The Structure and Operation of a Turing Machine
A Turing Machine consists of a long tape divided into squares, onto which symbols can be written and later erased, together with a read/write head (as in a tape recorder) which can write (or erase) symbols and also read them. Such reading and writing can only take place on the particular square where the read/write head is placed, but the head is capable of moving – one square at a time – in either direction. So by moving repeatedly left or right, any square on the tape can eventually be reached if required. (And the tape is potentially infinite in length: new tape is created whenever necessary so that the head never runs out of space.) Each square can contain at most one symbol, so writing a new symbol on a square automatically erases any previous symbol.
In order to "remember what it is doing", the Turing Machine has a very limited memory in the form of a "state", which can take any of a specified – and finite – range of values. One of these is the beginning state, from which computation starts. Computation then proceeds in the following way:
Read symbol from current square
Depending on the symbol read, and the current state:
Erase the symbol, or write a new one;
Move left or right on the tape;
Change to a new state.
Stage 2 here is governed by a "machine table" which states what operations (a), (b) and (c) are to be carried out for each combination of symbol read and current state. For a video showing a Turing machine in action (in the context of a discussion of their significance) see the first talk at https://www.philocomp.net/videos/turing.htm. [See also https://www.philocomp.net/computing/turing1936.htm, from which the Turing machine description above is taken.]
Implementing a Turing Machine as an ELIZA Script
ELIZA is well suited for straightforward implementation of a Turing machine, because it operates by transforming text strings, and a text string provides a natural representation of a Turing machine tape. Since ELIZA operates at the level of words, we represent each Turing machine symbol as a word, with spaces as separators between them, and we represent any blank square as an underscore “_”. In addition, we need to represent the current position of the read/write head on the tape, which can be done by using an asterisk “*” on each side of the relevant symbol (again separated by spaces). [Or we could use distinct symbols for the left and right of the current square, for example “L” and “R”.]
Turing machine states are represented by ELIZA keywords, and transitions between states are implemented as (potentially recursive) transitions from one keyword to another using the “PRE” operator as described in Weizenbaums’s paper.
Let us now turn to examine how this works in detail, before exhibiting a Turing machine script for detecting palindromes. This provides both a nice example, and an important one, because detection of palindromes is a task which is impossible for less powerful models of computation such as finite state machines.
(a) Keywords and Text Transformation within ELIZA
The general form of text transformation rules in an ELIZA script is
(keyword
((decomposition rule 1)
(reassembly rule 1.1)
(reassembly rule 1.2)
(…))
((decomposition rule 2)
(reassembly rule 2.1)
(reassembly rule 2.2)
(…))
…)
The words of the text entered by the user are checked sequentially to see whether each of them appears in the script as a keyword. If it does, then it is put onto a list of found keywords. Each keyword has a numeric precedence (0 by default), which determines where it should be added to the keyword list – it goes at the front if it is of higher precedence than the current keyword in that position, but otherwise it goes at the back. When a period, comma or the word “BUT” is encountered in the user’s text, keyword checking ends, unless no keywords have yet been found, in which case checking continues with any words that follow this delimiter.
Once keyword checking is complete, the keyword at the front of the keyword list is selected and the decomposition rules associated with this keyword are tried, in order, against the input text. The first decomposition rule that successfully matches the input text is selected and one of the associated reassembly rules is used to form ELIZA’s response to the input text. (If there are multiple reassembly rules associated with a given decomposition rule, they will be cycled through on successive matches of that decomposition rule.)
(b) Using the “PRE” Keyword for Recursive Rule Application
One of the reassembly rules allowed in an ELIZA script is called “PRE”. Joseph Weizenbaum describes this rule in his 1966 CACM paper (p. 41):
Under still other conditions it may be desirable to perform a preliminary transformation on the input text before subjecting it to the decompositions and reassemblies which finally yield the output text. For example, the keyword “you’re” should lead to the transformation rules associated with “you” but should first be replaced by a word pair. The dictionary entry for “you’re” is therefore:
(“you’re" = I’m ((0 I’m 0) (PRE (I AM 3) (=YOU))))
which has the following effect:
Whenever “you’re” is found in the input text, it is replaced by “I’m”.
If “you’re” is actually selected as the regnant keyword, then the input text is decomposed into three constituent parts, namely, all text in front of the first occurrence of “I’m”, the word “I’m” itself, and all the text following the first occurrence of “I’m”.
The reassembly rule beginning with the code “PRE” is encountered and the decomposed text reassembled such that the words “I AM” appear in front of the third constituent determined by the earlier decomposition.
Control is transferred, so to speak, to the transformation rules associated with the keyword “you”, where further decompositions etc. are attempted.
It is to be noted that the set
(PRE (I AM 3) (=YOU))
Is logically in the place of a reassembly rule and may therefore be one of many reassembly rules associated with the given decomposition.
The crucial point for our purposes is that this behaviour gives us the means of recursively jumping from one keyword to another (“you’re” to “you” in Weizenbaum’s example) while simultaneously changing the input text in specified ways. This is enough to enable us to implement a Turing machine.
(c) Constructing a Turing Machine
By exploiting the PRE keyword, we can construct a Turing machine as follows:
The written portion of the “tape” is represented by the input list of words. Each word is a “square” on the tape, with a blank square represented by the underscore “_”. The tape is assumed to be blank both before and after the written portion.
The current position of the Turing machine “read/write head” is marked by symbols that are not part of the Turing machine alphabet, one either side of the current head position. We use asterisks in the example below.
States are encoded as keywords. Each state (keyword) has one decomposition rule for each possible symbol under the head. The decomposition rule will match the tape only when the particular symbol is under the head (between the asterisks). The associated reassembly rule is a PRE rule that rewrites the tape according to the required change to the symbol, if any, and moves the head one square left or right, if such a move is required. Finally, the PRE rule tells ELIZA to continue processing the tape with the specified keyword, thus changing to a new state, if required.
Each state begins by extending the tape to the left (or right), if necessary, by appending an empty cell. The state is unchanged. The tape is extended only when there is no cell before (or after) the current head position. This makes the tape effectively infinite.
Script for a Turing Machine to Detect Palindromes
Below is a complete ELIZA script, which encodes a Turing Machine to decide whether the user’s input text is a palindrome of “A”s and “B”s.
(ELIZA CAN DECIDE IF A STRING OF LETTERS IS A PALINDROME.
TYPE THE WORD PALP FOLLOWED BY A STRING OF A AND B LETTERS,
WITH SPACES BETWEEN EACH LETTER. ELIZA WILL RESPOND TRUE IF
THE STRING IS A PALINDROME, OTHERWISE ELIZA RESPONDS FALSE.
EG. TYPE PALP A B B A AND ELIZA WILL RESPOND TRUE.)
(PALP
((PALP)
(PRE (* _ *) (=Q0))) ; position head at empty cell
((PALP A 0)
(PRE (* A * 3) (=Q0))) ; position head at first A
((PALP B 0)
(PRE (* B * 3) (=Q0))) ; position head at first B
((0)
(YOU MUST START WITH THE WORD PALP
AND FOLLOW THAT WITH ANY COMBINATION OF THE LETTERS
A AND B WITH SPACES BETWEEN EACH LETTER.)))
; Q=current state
; R=read this symbol at head
; W=write this symbol at head (blank means don't write anything)
; M=move head left (L) or right (R), or blank for don't move head
; Q'=new state
;
; In state Q, when the symbol at the head is R, then write W, move M
; and set the new state to Q'
; Q R W M Q'
(Q0
((* 0) (PRE (_ * 2) (=Q0)))
((0 *) (PRE (1 * _) (=Q0)))
((0 1 * A * 1 0) (PRE (1 2 _ * 6 * 7) (=Q1))) ; Q0 A _ R Q1
((0 1 * B * 1 0) (PRE (1 2 _ * 6 * 7) (=Q4))) ; Q0 B _ R Q4
((0 1 * _ * 1 0) (=QACCEPT))) ; Q0 _ QACCEPT
(Q1
((* 0) (PRE (_ * 2) (=Q1)))
((0 *) (PRE (1 * _) (=Q1)))
((0 1 * A * 1 0) (PRE (1 2 A * 6 * 7) (=Q1))) ; Q1 A R Q1
((0 1 * B * 1 0) (PRE (1 2 B * 6 * 7) (=Q1))) ; Q1 B R Q1
((0 1 * _ * 1 0) (PRE (1 * 2 * _ 6 7) (=Q2)))); Q1 _ L Q2
(Q2
((* 0) (PRE (_ * 2) (=Q2)))
((0 *) (PRE (1 * _) (=Q2)))
((0 1 * A * 1 0) (PRE (1 * 2 * _ 6 7) (=Q3))) ; Q2 A _ L Q3
((0 1 * B * 1 0) (=QREJECT)) ; Q2 B QREJECT
((0 1 * _ * 1 0) (=QACCEPT))) ; Q2 _ QACCEPT
(Q3
((* 0) (PRE (_ * 2) (=Q3)))
((0 *) (PRE (1 * _) (=Q3)))
((0 1 * A * 1 0) (PRE (1 * 2 * A 6 7) (=Q3))) ; Q3 A L Q3
((0 1 * B * 1 0) (PRE (1 * 2 * B 6 7) (=Q3))) ; Q3 B L Q3
((0 1 * _ * 1 0) (PRE (1 2 _ * 6 * 7) (=Q0)))); Q3 _ R Q0
(Q4
((* 0) (PRE (_ * 2) (=Q4)))
((0 *) (PRE (1 * _) (=Q4)))
((0 1 * A * 1 0) (PRE (1 2 A * 6 * 7) (=Q4))) ; Q4 A R Q4
((0 1 * B * 1 0) (PRE (1 2 B * 6 * 7) (=Q4))) ; Q4 B R Q4
((0 1 * _ * 1 0) (PRE (1 * 2 * _ 6 7) (=Q5)))); Q4 _ L Q5
(Q5
((* 0) (PRE (_ * 2) (=Q5)))
((0 *) (PRE (1 * _) (=Q5)))
((0 1 * A * 1 0) (=QREJECT)) ; Q5 A QREJECT
((0 1 * B * 1 0) (PRE (1 * 2 * _ 6 7) (=Q3))) ; Q5 B _ L Q3
((0 1 * _ * 1 0) (=QACCEPT))) ; Q5 _ QACCEPT
(QACCEPT
((0)
(TRUE)))
(QREJECT
((0)
(FALSE)))
(NONE
((0)
(TRY TYPING PALP A B A)
(TRY PALP A A A A)
(TRY PALP B A, ELIZA SHOULD RESPOND FALSE)
(TRY PALP B A B, ELIZA SHOULD RESPOND TRUE)))
(TURING
((0)
(MACHINE)))
(MEMORY TURING
(0 = TURING MACHINE)
(0 = TURING MACHINE)
(0 = TURING MACHINE)
(0 = TURING MACHINE))
How the Script Works
This particular Turing machine requires that the symbols on the tape be “A”, “B” and “_”, with the underscore representing an empty cell. In addition, two asterisks “*” are used during processing to represent the position of the read/write head.
Suppose we start by inputting “PALP A B B A”, to test whether “A B B A” is a palindrome. Then the keyword “PALP” is identified, and the text as a whole is found to match the decomposition rule shown below, together with its corresponding reassembly rule:
((PALP A 0)
(PRE (* A * 3) (=Q0)))
Here “PALP” and “A” match literally with the first two fields of the decomposition rule, leaving the third field “0” (which can match any number of words) to match with “B B A”. Then the reassembly rule transforms the text to “* A *” followed by field 3 from the decomposition rule. Hence the text becomes “* A * B B A”, and control is transferred to keyword “Q0”, as desired. All this has the effect of placing the read-write head at the first position in the text.
Within the script for keyword “Q0”, the first decomposition/reassembly rule pair is designed to deal with the situation in which the text begins with an asterisk:
((* 0) (PRE (_ * 2) (=Q0)))
With our text as “* A * B B A”, the initial asterisk matches literally, and “0” then matches with “A * B B A”. The reassembly rule then transforms the text into “_ *” followed by field 2, yielding “_ * A * B B A”. This therefore adds a blank square to the beginning of the text, ensuring that the read/write head always has a square to its left-hand side. The reassembly rule finally returns control recursively to keyword “Q0”, but now with the text being
“_ * A * B B A”. This in turn matches against the decomposition/reassembly rule:
((0 1 * A * 1 0) (PRE (1 2 _ * 6 * 7) (=Q1)))
[In the script, this rule is annotated with “; Q0 A _ R Q1” which indicates that here we are in state Q0 with an “A” under the read/write head; this “A” is to be replaced by “_”, the head is to move to the right, and the machine is to switch into state Q1.]
Here the first field “0” matches nothing, the second field “1” (which can match any single word) matches “_”, then “* A *” matches literally, the sixth field “1” matches “B”, and the final seventh field matches “B A”. The reassembly rule transforms the text into field 1 (nothing) followed by field 2 (“_”), then “_ *”, then field 6 (“B”), “*”, and finally field 7 (“B A”). Hence the text is now “_ _ * B * B A”, so the “A” under the head has been erased (replaced by a blank) and the head moved one cell to the right. Finally, control is transferred to keyword “Q1”.
That detailed explanation of the first few transformations should provide enough clues to work out how the rest of the script operates. To summarise briefly, the machine erases the “A” or “B” at the beginning of the sequence (applying the rule for keyword/state Q0), then travels to the end, either in state Q1 (if the first character was “A”) or Q4 (if a “B”). When it reaches the end (by finding “_”), it moves left to the previous square, transferring into state Q2 (if “A”) or Q5 (if “B”). There it expects to find a corresponding “A” or “B” (respectively), which it also erases, before entering state Q3 to return to the beginning where, after finding “_”, it moves right and transfers into state Q0 to repeat the process.
===================================================================================================
Here are some traces of the ELIZA "program" (script) above executing several examples. Because most of the action takes place internally, via PRE calls, someone actually having a conversation with ELIZA won't see anything except the result (true or false). Here Anthony Hay has instrumented his ELIZA clone to display the "tape" (sentence) as it executes recursively through the PRE calls. First we just show the tape, then some more detailed versions that include the states and pattern matches and re-assemblies. (This and other examples from Turing's paper and execution traces are at: https://github.com/jeffshrager/elizagen.org/tree/master/TuringCompleteness, and Anthony Hay's ELIZA is here: https://github.com/anthay/ELIZA)
PALP A B B A A A B B A
* A * B B A A A B B A
_ * A * B B A A A B B A
_ _ * B * B A A A B B A
_ _ B * B * A A A B B A
_ _ B B * A * A A B B A
_ _ B B A * A * A B B A
_ _ B B A A * A * B B A
_ _ B B A A A * B * B A
_ _ B B A A A B * B * A
_ _ B B A A A B B * A *
_ _ B B A A A B B * A * _
_ _ B B A A A B B A * _ *
_ _ B B A A A B B A * _ * _
_ _ B B A A A B B * A * _ _
_ _ B B A A A B * B * _ _ _
_ _ B B A A A * B * B _ _ _
_ _ B B A A * A * B B _ _ _
_ _ B B A * A * A B B _ _ _
_ _ B B * A * A A B B _ _ _
_ _ B * B * A A A B B _ _ _
_ _ * B * B A A A B B _ _ _
_ * _ * B B A A A B B _ _ _
_ _ * B * B A A A B B _ _ _
_ _ _ * B * A A A B B _ _ _
_ _ _ B * A * A A B B _ _ _
_ _ _ B A * A * A B B _ _ _
_ _ _ B A A * A * B B _ _ _
_ _ _ B A A A * B * B _ _ _
_ _ _ B A A A B * B * _ _ _
_ _ _ B A A A B B * _ * _ _
_ _ _ B A A A B * B * _ _ _
_ _ _ B A A A * B * _ _ _ _
_ _ _ B A A * A * B _ _ _ _
_ _ _ B A * A * A B _ _ _ _
_ _ _ B * A * A A B _ _ _ _
_ _ _ * B * A A A B _ _ _ _
_ _ * _ * B A A A B _ _ _ _
_ _ _ * B * A A A B _ _ _ _
_ _ _ _ * A * A A B _ _ _ _
_ _ _ _ A * A * A B _ _ _ _
_ _ _ _ A A * A * B _ _ _ _
_ _ _ _ A A A * B * _ _ _ _
_ _ _ _ A A A B * _ * _ _ _
_ _ _ _ A A A * B * _ _ _ _
_ _ _ _ A A * A * _ _ _ _ _
_ _ _ _ A * A * A _ _ _ _ _
_ _ _ _ * A * A A _ _ _ _ _
_ _ _ * _ * A A A _ _ _ _ _
_ _ _ _ * A * A A _ _ _ _ _
_ _ _ _ _ * A * A _ _ _ _ _
_ _ _ _ _ A * A * _ _ _ _ _
_ _ _ _ _ A A * _ * _ _ _ _
_ _ _ _ _ A * A * _ _ _ _ _
_ _ _ _ _ * A * _ _ _ _ _ _
_ _ _ _ * _ * A _ _ _ _ _ _
_ _ _ _ _ * A * _ _ _ _ _ _
_ _ _ _ _ _ * _ * _ _ _ _ _
_ _ _ _ _ * _ * _ _ _ _ _ _
_ _ _ _ _ * _ * _ _ _ _ _ _
TRUE
=================================================
palp a
TRUE
STATE INPUT MATCH ASSMBL
-------------------------------------------------
PALP PALP A PALP A 0 ( PRE ( * A * 3 ) ( =Q0 ) )
Q0 : * A * * 0 ( PRE ( _ * 2 ) ( =Q0 ) )
Q0 : _ * A * 0 * ( PRE ( 1 * _ ) ( =Q0 ) )
Q0 : _ * A * _ 0 1 * A * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ * _ * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ * _ * _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q2 ) )
Q2 : _ * _ * _ _ 0 1 * _ * 1 0 =QACCEPT
QACCEPT _ * _ _ 0 TRUE
=================================================
palp a b
FALSE
STATE INPUT MATCH ASSMBL
-------------------------------------------------
PALP PALP A B PALP A 0 ( PRE ( * A * 3 ) ( =Q0 ) )
Q0 : * A * B * 0 ( PRE ( _ * 2 ) ( =Q0 ) )
Q0 : _ * A * B 0 1 * A * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ * B * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ * B * _ 0 1 * B * 1 0 ( PRE ( 1 2 B * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B * _ * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ B * _ * _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q2 ) )
Q2 : _ _ * B * _ _ 0 1 * B * 1 0 =QREJECT
QREJECT * B * _ _ 0 FALSE
=================================================
palp a b a
TRUE
STATE INPUT MATCH ASSMBL
-------------------------------------------------
PALP PALP A B A PALP A 0 ( PRE ( * A * 3 ) ( =Q0 ) )
Q0 : * A * B A * 0 ( PRE ( _ * 2 ) ( =Q0 ) )
Q0 : _ * A * B A 0 1 * A * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ * B * A 0 1 * B * 1 0 ( PRE ( 1 2 B * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B * A * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ B * A * _ 0 1 * A * 1 0 ( PRE ( 1 2 A * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B A * _ * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ B A * _ * _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q2 ) )
Q2 : _ _ B * A * _ _ 0 1 * A * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q3 ) )
Q3 : _ _ * B * _ _ _ 0 1 * B * 1 0 ( PRE ( 1 * 2 * B 6 7 ) ( =Q3 ) )
Q3 : _ * _ * B _ _ _ 0 1 * _ * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q0 ) )
Q0 : _ _ * B * _ _ _ 0 1 * B * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q4 ) )
Q4 : _ _ _ * _ * _ _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q5 ) )
Q5 : _ _ * _ * _ _ _ 0 1 * _ * 1 0 =QACCEPT
QACCEPT * _ * _ _ _ 0 TRUE
=================================================
palp a b b a
TRUE
STATE INPUT MATCH ASSMBL
------------------------------------------------------
PALP PALP A B B A PALP A 0 ( PRE ( * A * 3 ) ( =Q0 ) )
Q0 : * A * B B A * 0 ( PRE ( _ * 2 ) ( =Q0 ) )
Q0 : _ * A * B B A 0 1 * A * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ * B * B A 0 1 * B * 1 0 ( PRE ( 1 2 B * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B * B * A 0 1 * B * 1 0 ( PRE ( 1 2 B * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B B * A * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ B B * A * _ 0 1 * A * 1 0 ( PRE ( 1 2 A * 6 * 7 ) ( =Q1 ) )
Q1 : _ _ B B A * _ * 0 * ( PRE ( 1 * _ ) ( =Q1 ) )
Q1 : _ _ B B A * _ * _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q2 ) )
Q2 : _ _ B B * A * _ _ 0 1 * A * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q3 ) )
Q3 : _ _ B * B * _ _ _ 0 1 * B * 1 0 ( PRE ( 1 * 2 * B 6 7 ) ( =Q3 ) )
Q3 : _ _ * B * B _ _ _ 0 1 * B * 1 0 ( PRE ( 1 * 2 * B 6 7 ) ( =Q3 ) )
Q3 : _ * _ * B B _ _ _ 0 1 * _ * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q0 ) )
Q0 : _ _ * B * B _ _ _ 0 1 * B * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q4 ) )
Q4 : _ _ _ * B * _ _ _ 0 1 * B * 1 0 ( PRE ( 1 2 B * 6 * 7 ) ( =Q4 ) )
Q4 : _ _ _ B * _ * _ _ 0 1 * _ * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q5 ) )
Q5 : _ _ _ * B * _ _ _ 0 1 * B * 1 0 ( PRE ( 1 * 2 * _ 6 7 ) ( =Q3 ) )
Q3 : _ _ * _ * _ _ _ _ 0 1 * _ * 1 0 ( PRE ( 1 2 _ * 6 * 7 ) ( =Q0 ) )
Q0 : _ _ _ * _ * _ _ _ 0 1 * _ * 1 0 =QACCEPT
QACCEPT _ * _ * _ _ _ 0 TRUE