Back to the Turing Machine
One of these ideas was to create Fizz Buzz on a Turing Machine (abbreviated TM) - you know, the thing with the tape of zeroes and ones. Last summer I created its building blocks, i.e. symbols,
Tape, TuringMachine and TransitionTable classes. These parts built an Universal Turing Machine (abbreviated UTM), which ran any concrete TM. On top I added transition tables for the basic structures required by Fizz Bizz, e.g. numbers (encoded as binary) and operations to INC and compare them. Inspired (or biased) by assembly, I unknowingly recreated a Von Neumann architecture where some part of the tape contained the program code, specific symbols for each operation, and another part contained the working memory. Now I had a machine on top of a machine.
ArithmeticThe best part about "Entertainment Coding" is that you can stop whenever you want. I often stop when I have proven my idea. I pass on filling in all the details. And there are a lot of details to fill in for a Turing complete assembly - which I need for Fizz Bizz. The numbers are encoded as their bits. Moving the data cursor right or left one number needs only a few states and transitions. Increment's (
INC) transition table, shown in the previous article, has around 8 lines. Decrement is the same. Comparing two numbers for being less-than or being equal-to needs 28 lines and duplicating a number to the next space on the right has already 34 lines. The number of state transitions grows with the number of cells involved (e.g. Which bit is this?), overflow (e.g. Do I have to add 1 to the bit because of the previous operation?) and number of operands (e.g. Do I have to move right to continue?). Adding or subtracting two numbers is the same flow, with more moving the read-write head and keeping the overflow. It is possible and much work, so skip it.Flow Control
What about flow control? For Fizz Buzz I need two kinds of flow control:
- A conditional to check if a number is equal another number. If they are equal, the following code is run, else the code is skipped. Skipping next instructions is a jump forward towards the end of the "if body", defined by the symbol ';'. (Why use a semicolon? I do not know, probably I did too much Java in my life ;-) Luckily I only need to check if a number is equal to 0, which is much simpler than comparing to an arbitrary number.
- For looping - at the end of the loop - I need to check if a number is smaller than another number. This is like point 1 above. Then jump back to the beginning. This is a jump backwards to the start of the "loop body". I need a
GOTOand a loop label as target to do this.
'L' ... start of the loop
'i' ... current += 1
'z' ... if (current % 15) == 0 then
// write "FizzBuzz"
'g' ... continue
';' ... end if
// similar block for 3
// similar block for 5
// write current as string
'<' ... if current < 100 then
'g' ... continue
';' ... end if
'h' ... halt programBecause I miss else the body of each if must end the loop prematurely - in some programming languages called continue. Thus the last if checks the loop exit, i.e. the upper limit, e.g. 100. The last number must not be Fizz nor Buzz nor FizzBuzz.Time for some low level details: Here is the transition table of
GOTO:| Step | state | symbol | newState | newSymbol | direction |
|---|---|---|---|---|---|
| (1) | Ip_SwitchRight | 'g' | Ip_Goto | same | L |
| (2) | Ip_Goto | 'P' | same | same | L |
| (3) | Ip_Goto | 'h' | Ip_GotoRightHalt | 'P' | R |
| Ip_GotoRightHalt | 'P' | Ip_Goto | 'h' | L | |
| Ip_Goto | 'd' | Ip_GotoRightDup | 'P' | R | |
| Ip_GotoRightDup | 'P' | Ip_Goto | 'd' | L | |
| Ip_Goto | 'i' | Ip_GotoRightInc | 'P' | R | |
| Ip_GotoRightInc | 'P' | Ip_Goto | 'i' | L | |
| Ip_Goto | 'r' | Ip_GotoRightRightMove | 'P' | R | |
| Ip_GotoRightRightMove | 'P' | Ip_Goto | 'r' | L | |
| Ip_Goto | 'l' | Ip_GotoRightLeftMove | 'P' | R | |
| Ip_GotoRightLeftMove | 'P' | Ip_Goto | 'l' | L | |
| Ip_Goto | '=' | Ip_GotoRightEqual | 'P' | R | |
| Ip_GotoRightEqual | 'P' | Ip_Goto | '=' | L | |
| Ip_Goto | '<' | Ip_GotoRightLess | 'P' | R | |
| Ip_GotoRightLess | 'P' | Ip_Goto | '<' | L | |
| Ip_Goto | ';' | Ip_GotoRightEqualEnd | 'P' | R | |
| Ip_GotoRightEqualEnd | 'P' | Ip_Goto | ';' | L | |
| (4) | Ip_Goto | 'L' | Ip_Restart | same | R |
Transition (1) begins the
GOTO states. Transition (2) starts moving left and skips the instruction pointer. Transition (3) moves the instruction pointer along each and every skipped instruction. Whenever I add a new instruction I have to update conditional and loop code, which is boring. (4) Goto's state transitions finish when it sees the symbol 'L'. Then the instruction process restarts with state Ip_Restart by looking at the next instruction right of the instruction pointer.The Whole "Language"
Till now I created the following symbols:
| symbol | memory | meaning |
|---|---|---|
| '0'/'1' | data | a bit of a number. |
| '$' | data | separator of a number or memory slot - a "byte" if you like. |
| 'C' | data | data Cursor marking the current number on its right. |
| 'P' | code | instruction Pointer left of the next instruction. |
| 'h' | instruction | halt, stop the TM. |
| 'l'/'r' | instruction | move the cursor one number to the left or right. |
| 'i' | instruction | increment the current number by one and move cursor right. |
| 'e' | instruction | decrement the current number. |
| 'd' | instruction | duplicate current number to the right. |
| '3' | instruction | write the digits of 3 into the current number. |
| '<' | instruction | jump to end of block if current is not < next number. |
| '=' | instruction | jump to end of block if current is not = next number. |
| 'z' | instruction | jump to end of block if current number is not 0. |
| ';' | label | mark the end of the (conditional) block. |
| 'g' | instruction | jump backwards (moving 'P' left) until the label 'L'. |
| 'L' | label | Loop label for goto (backwards) jump. |
Instruction '3' is special, as would be '5' and 15. Data values are on the tape and copied around. It might save me some hassle if I can write arbitrary numbers programmatically. Then d3ll%lz...;lll would be the code to check for multiplies of 3 - if I had '%'. All my programs (till now) will match the regular expression P[hdierl3=<z;gL]+C([01]{7}\\$)*.I need modulo ('%'), which extends subtraction (which extends decrement). Modulo is hard, too complicated for me to write it as state transitions. I could write a macro, i.e. separate code that gets executed whenever the UTM reads a '%'. This would be like Microcode of modern CPUs. Or I could create subroutines. If I avoid nesting them, a single instruction pointer symbol, e.g. 'R', as return address would be sufficient. For example, when the UTM reads 's', it writes the 'R' instead of the 'P'. Then it searches right for 'S' which is the label to start the subroutine and executes until it reads 'r' for return. On 'r' the instruction pointer goes back to 'R'. Four new symbol 'srSR' (2 instructions, 1 label, 1 pointer). Regular program flow can never see 'S' or 'R' and I omit adding them to if or goto. The 's' might be inside a loop or conditional. The 's' and 'r' are gotos looking in specific directions for specific labels, nothing conceptionally new.
The "Actual" Program
I have enough of this. This is a Turing Tarpit, a (esoteric) programming language that is universal but impractical and difficult because it offers no support for common tasks. [...] Using such a language is a form of mathematical recreation. Yes I can finish Fizz Buzz, but it is no fun. To conclude, here is my final piece of code to create the numbers from 1 to 16 on the tape:
P Lrdllldlil<lg; // loop creating numbers i // fix last element llllllllllllllll // go back all = "l" * limit hC 0000001$ // from 1 0001111$ // to limit - 1I hope you had fun following me on my quest. The whole TM, UTM and transition logic is on my Git. I now appreciate how high level assembly is.
