Corrected transitions are boldface.
| State | Tape symbol | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | c | L | R | b | (m0) | (m1) | (mc) | (mL) | (mR) | (mb) | |
| A | A,0,R | A,1,R | A,c,R | A,L,R | A,R,R | B,(mc),R | ||||||
| B | B,0,R | B,1,R | B,c,R | B,L,R | B,R,R | C0,(m0),L | C1,(m1),L | CB,(mb),L | ||||
| CB | CB,0,L | CB,1,L | CB,c,L | CB,L,L | CB,R,L | DB,c,R | ||||||
| C0 | C0,0,L | C0,1,L | C0,c,L | C0,L,L | C0,R,L | D0,c,R | ||||||
| C1 | C1,0,L | C1,1,L | C1,c,L | C1,L,L | C1,R,L | D1,c,R | ||||||
| DB | V,0,L | E,(m1),L | ||||||||||
| D0 | D0,0,R | D0,1,R | DB,c,R | D0,L,R | D0,R,R | |||||||
| D1 | D1,0,R | D1,1,R | D0,c,R | D1,L,R | D1,R,R | |||||||
| E | E,0,L | E,1,L | F,c,L | E,L,L | E,R,L | |||||||
| F | E,0,L | E,1,L | G,c,L | E,L,L | E,R,L | |||||||
| G | E,0,L | E,1,L | H,c,R | E,L,L | E,R,L | |||||||
| H | I,c,R | |||||||||||
| I | J,(mc),R | |||||||||||
| J | J,0,R | J,1,R | J,c,R | J,L,R | J,R,R | KL,1,R | ||||||
| KL | ML,(m1),L | TL,L,R | TR,R,R | |||||||||
| ML | ML,0,L | ML,1,L | ML,c,L | ML,L,L | ML,R,L | NL,c,R | ||||||
| NL | NL,0,R | NL,1,R | PL,c,R | NL,L,R | NL,R,R | NR,(m1),R | ||||||
| PL | NL,0,R | NL,1,R | SL,(mc),R | NL,L,R | NL,R,R | NR,(m1),R | ||||||
| SL | SL,0,R | SL,1,R | SL,c,R | SL,L,R | SL,R,R | KL,1,R | ||||||
| KR | MR,(m1),R | TL,L,R | TR,R,R | |||||||||
| MR | MR,0,R | MR,1,R | MR,c,R | MR,L,R | MR,R,R | NR,c,R | ||||||
| NR | NR,0,R | NR,1,R | PR,c,R | NR,L,R | NR,R,R | |||||||
| PR | NR,0,R | NR,1,R | SR,(mc),L | NR,L,R | NR,R,R | |||||||
| SR | SR,0,L | SR,1,L | SR,c,L | SR,L,L | SR,R,L | KR,1,R | ||||||
| TL | TL-0,0,R | TL-1,1,R | ||||||||||
| TR | TR-0,0,R | TR-1,1,R | ||||||||||
| TL-0 | TL-0,0,R | TL-0,1,R | TL-0,c,R | TL-0,L,R | TL-0,R,R | U,0,L | U,0,L | TL-0,(mc),R | U,0,L | |||
| TL-1 | TL-1,0,R | TL-1,1,R | TL-1,c,R | TL-1,L,R | TL-1,R,R | U,1,L | U,1,L | TL-1,(mc),R | U,1,L | |||
| TR-0 | TR-0,0,R | TR-0,1,R | TR-0,c,R | TR-0,L,R | TR-0,R,R | U,0,R | U,0,R | TR-0,(mc),R | U,0,R | |||
| TR-1 | TR-1,0,R | TR-1,1,R | TR-1,c,R | TR-1,L,R | TR-1,R,R | U,1,R | U,1,R | TR-1,(mc),R | U,1,R | |||
| U | C0,(m0),L | C1,(m1),L | CB,(mb),L | |||||||||
| V | V,0,L | V,1,L | W,c,L | V,L,L | V,R,L | |||||||
| W | V,0,L | V,1,L | X1,c,R | V,L,L | V,R,L | |||||||
| X1 | X2,c,R | |||||||||||
| X2 | X3,0,R | |||||||||||
| X3 | X4,c,R | |||||||||||
| X4 | X5,0,R | |||||||||||
| X5 | X6,c,R | |||||||||||
| X6 | Y,0,R | |||||||||||
| Y | ||||||||||||
An empty transition is a reject (except for those in state Y).
The highlighted transition for state DB is corrected. The original was missing the direction the tape head should move.
The highlighted transitions for states TL-0, TL-1, TR-0, and TR-1 were omitted in Hopcroft & Ullman's text.
The tape symbols (mL) and (mR) have no transitions. I assume they were included to catch invalid input tapes, which should be rejected.
Last updated 4 April 2003
http://www.rdrop.com/~half/General/UTM/UTMStateTable.html
All contents ©2000-2002 Mark L. Irons except the original UTM state table, which is ©1969 Hopcroft & Ullman.