TT02 W5S8
A core for Watanabe's 5-symbol, 8-state universal Turing machine on Tiny Tapeout 02
The transition function for Watanabe’s 5-symbol, 8-state universal Turing machine on Tiny Tapeout 02
The machine has 5 symbols - 0, 1, *, 0’, and 1’ - and 8 states - A, B, C, D, E, F, G, and H.
The transition function of the machine is defined by the following 3 tables, which specify the next state, new symbol, and movement direction along the tape for all possible combinations of current state (in the first column) and input symbol (in the top row).
Next state:
| 0 | 1 | * | 0' | 1' | |
|---|---|---|---|---|---|
| A: | B | C | A | E | A |
| B: | B | B | D | G | H |
| C: | C | C | B | G | H |
| D: | C | E | A | D | D |
| E: | D | F | E | D | E |
| F: | F | F | G | B | B |
| G: | A | A | F | G | G |
| H: | A | A | F | H | H |
New symbol:
| 0 | 1 | * | 0’ | 1’ | |
|---|---|---|---|---|---|
| A: | * | * | * | 0 | 1 |
| B: | 0’ | 1’ | 0’ | 0 | 1 |
| C: | 0’ | 1’ | 0’ | 0’ | 1’ |
| D: | 0 | 1’ | * | * | 1’ |
| E: | 0 | 1’ | 0’ | * | 1’ |
| F: | 0’ | 1’ | 0 | 0 | 1 |
| G: | 0 | 1 | 0 | 0 | 1 |
| H: | 0 | 1 | 1 | 0 | 1 |
Direction:
| 0 | 1 | * | 0' | 1' | |
|---|---|---|---|---|---|
| A: | L | L | R | L | R |
| B: | L | L | L | R | R |
| C: | L | L | L | R | R |
| D: | R | R | R | L | L |
| E: | R | L | R | L | R |
| F: | L | L | R | R | R |
| G: | R | R | L | R | R |
| H: | L | L | L | R | R |
The 40 state + symbol input combinations on the TT02 demo board:
The output is on the 7 segment display, with the direction in bit 1 (upper right), the next state in bits 2, 3, and 4 (lower left, bottom, and lower right), and the new symbol in bits 5, 6, and 7 (upper left, center, and decimal point).
Given a description of another machine encoded on an input tape using the 5-symbol alphabet, a Turing machine constructed using w5s8 (i.e. the w5s8 core plus a tape read/write head and an infinite tape) can simulate an arbitrary Turing machine.
For example, the 2-state (X and Y), 2-symbol (0 and 1) busy beaver (BB-2) machine is
| 0 | 1
X | 1 R Y 1 L Y
Y | 1 L X 1 R haltand starts with an empty (all zero) input tape.
On this 5-symbol, 8-state machine, the corresponding input tape for BB-2 is 327 symbols for the description of the BB-2 machine, plus space on the right end for the tape of the simulated machine (20 spaces here):
**111111*111111111111111**11111111111111111111111111*111111111111111111111111111111111111111111111111111111*01010101010101001001010101010101010101010011010101010101010101010101010101010101010101010101010101001101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010010000000000000000000000(generated with convert.py)
BB-2 takes 5 steps and halts on the 6th after writing a total of 4 1s to the tape. To simulate BB-2, W5S8 takes 62962 steps.