On my search for harder coding challenges, join me implementing Fizz Buzz using a Turing machine where I dive into Turing machines from a practical coding perspective using Java. In the
previous part I finally understood Turing machines (TM) and created a Universal Turing Machine (UTM) using a
Tape and
TuringMachine classes. This is the second part.
Fizz Buzz
I want to implement Fizz Buzz but I have no idea how to start. A simple implementation in Java might be:
for (i = 1; i <= 100; i++) { // line 1
if (i % 3*5 == 0)
print("FizzBuzz");
else if (i % 3 == 0)
print("Fizz");
else if (i % 5 == 0)
print("Buzz");
else
print(i);
}Fizz Buzz is an easy problem, still it needs several programming constructs: Looping or sequences, conditional logic, arithmetic with integers including division for the remainder, strings and some form of input and output. The input is the number of lines required, in the code above hardcoded to 100, and the display showing the result, e.g.
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
What is the end state when I miss a display? For a TM the input will be the number on the tape and the output will be the list of strings on the tape again.
Representing Numbers
I am overwhelmed. When working katas, exercises or
new languages, I usually create the code bottom up, making things up on my way. Following that approach, I have to figure out individual operations first, then will I combine them into more powerful programs. For Fizz Buzz I first need to count from one to 100, incrementing by one. The smallest (binary) space to represent the number 100 needs seven bits which are seven cells on the tape containing a '0' or '1' followed by a separator '$', e.g. 100 would be
1100100$ on the tape. (To make my life easier, I assume the set of symbols contains arbitrary characters. After all each character is a sequence on bits anyway.) The separator helps because it avoids keeping track of positions inside the sequence of working with bits during some operations. (This is one of many design options. Another approach would be to store the position of each bit next to the bit on the tape.)
Incrementing Numbers
The first operation I need is
INC (increment by 1). Increment, an x86 assembly op-code, adds 1 to an unsigned integer operand. (Now - when writing this - I see why I ended up where I ended up. My first idea for a building block was a CPU assembly operation on a sequence of bits. From there I was following the given direction...) If you never did any assembly, let me explain
INC operating on a binary numbers. Let's assume a value, e.g. 78, binary
1001110. The increment adds 1,
01001110
+ 1
--------
1001111
Like adding regular (Arabic base 10) numbers, addition starts most left. The 1 adds to the 0 and we are done. In short, if there is a '0' bit, it becomes a '1' and that's it. So 78 becomes 79. Let's increment it again:
01001111
+ 1
--------
1001110
+ 1 ... overflow from the first digit
--------
1001100
+ 1 ... overflow from the second digit and so on
--------
1010000
which is 80. In short, if there is a '1' bit, it becomes a '0' and
INC continues incrementing left with the overflow.
INC on the UTM
Working on the tape of the TM, the algorithm to increment the number right of the read/write head is:
- Move the read/write head right until the end of the number (i.e. until the '$') to do the increment.
- Work backwards, i.e. move left to increment.
- If there is a '0', then write a '1' which finishes increment - and start moving right to the end.
- If there is a '1', then write a '0' and continue incrementing left with the overflow bit.
- In the end move right until the '$' to leave the read/write head in a consistent state.
The last bit must not overflow. Increment's transition table is
| Step | state | symbol | newState | newSymbol | direction |
|---|
| (1) | Inc | any | Inc_MoveRightAndInc | same | R |
| | Inc_MoveRightAndInc | '0' | Inc_MoveRightAndInc | same | R |
| | Inc_MoveRightAndInc | '1' | Inc_MoveRightAndInc | same | R |
| (2) | Inc_MoveRightAndInc | '$' | Inc_IncToTheLeft | same | L |
| (3) | Inc_IncToTheLeft | '0' | Inc_DoneMoveRight | '1' | none |
| (4) | Inc_IncToTheLeft | '1' | Inc_IncToTheLeft | '0' | L |
| (5) | Inc_DoneMoveRight | '0' | Inc_DoneMoveRight | same | R |
| | Inc_DoneMoveRight | '1' | Inc_DoneMoveRight | same | R |
| (T) | Inc_DoneMoveRight | '$' | Halt | same | none |
This table is a standalone test program a.k.a. a Turing machine. Line (T) stops after incrementing a given number. I can unit test the code comparing tapes, e.g.
@Test
void incZero() {
transitions.addIncTo(table);
createMachineWith("0000000$", Q.Inc, table);
machine.loop();
assertTapeEquals("0000001$");
}
@Test
void incOne() {
transitions.addIncTo(table);
createMachineWith("0000001$", Q.Inc, table);
machine.loop();
assertTapeEquals("0000010$");
}
@Test
void incToMax() {
transitions.addIncTo(table);
createMachineWith("0111111$", Q.Inc, table);
machine.loop();
assertTapeEquals("1000000$");
}DEC (Decrement by 1) is the same with '0' and '1' switched. Now I know how to build individual operations.
More Operations
Next operation is
DUP (duplicate a number). Things get cumbersome because the state of the current bit, i.e. if
DUP is copying '0', '1' or '$' eight places to the right has to be encoded in the states. For example the transition table to duplicate a '0' is
| state | symbol | newState | newSymbol | direction |
|---|
| Dup | '0' | Dup_Move7RightAndWrite0 | same | R |
| Dup_Move7RightAndWrite0 | any | Dup_Move6RightAndWrite0 | same | R |
| Dup_Move6RightAndWrite0 | any | Dup_Move5RightAndWrite0 | same | R |
| Dup_Move5RightAndWrite0 | any | Dup_Move4RightAndWrite0 | same | R |
| Dup_Move4RightAndWrite0 | any | Dup_Move3RightAndWrite0 | same | R |
| Dup_Move3RightAndWrite0 | any | Dup_Move2RightAndWrite0 | same | R |
| Dup_Move2RightAndWrite0 | any | Dup_Move1RightAndWrite0 | same | R |
| Dup_Move1RightAndWrite0 | any | Dup_Write0AndMove7Back | same | R |
| Dup_Write0AndMove7Back | any | Dup_Move7LeftAndStartAgain | '0' | none |
There are 9 state transitions for each "bit" - to "remember" the bit - and additional 7 states to move left again and start over, giving a total of 34 states for my simplified transition table allowing shortcuts for any symbol etc.
I am still implementing line 1 in the code on top of the page:,Counting from one to 100, incrementing by one. To create a loop, I need to start with one (
0000001$), duplicate it, increment the new number, and repeat while it is less than 100 or until it is 100. The instructions
LESS and
EQUAL are similar to
DUP. The current symbol has to be "remembered" in the states, the tape has to move eight places right and the comparison with the symbol there determines the result of the operation, then the tape has to move seven places left again and restart the operation.
Combining Operations
I started with x86 operations and I follow the idea further. I dislike duplicating
INC or other states so I create a lookup table - an area on the tape that would be holding the program, think
Code segment from x86 architecture before x86-64. The read/write head will have to move between the code and the data (think
Data segment) and I need markers for both positions. Let 'P' be the Instruction Pointer (usually called IP) and 'C' be a cursor marking the last position the read/write head had when working with data. Each operation will
- Move the instruction pointer to the next instruction by switching the letter of the operation with 'P'.
- Move the read/write head right to the cursor 'C'. There replace the cursor with the separator '$'.
- Perform the operation. Each operation must end with the read/write head positioned at a separator.
- Set the new cursor position.
- Move the read/write head back to the instruction pointer
- and start over.
Storing the program and the data in the same place, i.e. the tape, makes this a
Von Neumann architecture. When the UTM is processing instructions in the left side of the tape, it cannot work with data, which is on the right side of the data and vice versa. The
term "von Neumann architecture" refers to any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time (since they share a common bus) says Wikipedia.
INC as Instruction
Increment's extended, full transition table is
| Step | state | symbol | newState | newSymbol | direction |
|---|
| (1) | Ip_SwitchRight | 'i' | Ip_SwitchLeftInc | 'P' | L |
| | Ip_SwitchLeftInc | 'P' | Code_Inc | 'i' | none |
| (2) | Code_Inc | 'C' | Inc | '$' | R |
| | Code_Inc | any | same | same | R |
| (3) | Inc | any | Inc_MoveRightAndInc | same | R |
| | Inc_MoveRightAndInc | '0' | Inc_MoveRightAndInc | same | R |
| | Inc_MoveRightAndInc | '1' | Inc_MoveRightAndInc | same | R |
| | Inc_MoveRightAndInc | '$' | Inc_IncToTheLeft | same | L |
| | Inc_IncToTheLeft | '0' | DoneMoveRight | '1' | none |
| | Inc_IncToTheLeft | '1' | Inc_IncToTheLeft | '0' | L |
| | DoneMoveRight | '0' | DoneMoveRight | same | R |
| | DoneMoveRight | '1' | DoneMoveRight | same | R |
| (4) | DoneMoveRight | '$' | Ip_Restart | 'C' | none |
| (6) | Ip_Restart | 'P' | Ip_SwitchRight | same | R |
| (5) | Ip_Restart | any | same | same | L |
and its test
@Test
void inc() {
createMachineWith("PihC0000000$", Q.Ip_Restart, transitions.create());
machine.loop();
assertTapeEquals("ihP$0000001C");
}Letters 'i' and 'h' represent operations
INC and
HALT. After execution the instruction pointer moved two places to the right and the data cursor moved one number entry to the right.
Other Instructions
The extension of the partial transition tables of
DUP,
LESS,
EQUAL and operations to move the cursor left and right as instructions 'd', '<', '=', 'l' and 'r' is the same. States
DoneMoveRight and
Ip_Restart are generic and used by most of these instructions. See the
full transition table here.
This concludes the second part of my Turing Machine exploration. I spent too much time formatting transition tables. Now I have a machine on top of a machine. I made the problem easier by adding another level of indirection, an application of the
Fundamental theorem of software engineering. ;-) Stay tuned for
part three.
Exercises and Books on Refactoring
