Showing posts with label Turing machine. Show all posts
Showing posts with label Turing machine. Show all posts

28 September 2026

Finally Fizz Buzz Turing Machine

Now that our GenAI agents are doing all coding, what does remain for geek fun? I do not mean developing side projects or open source, I mean fiddling with code, tweaking it, exploring constructs like Only Exceptions for Flow Control. Such coding activities used to be practice or learning. What is their use now? At least they are entertaining (me). I use the tag Coding Fun to mark ideas of educational entertaining hobby coding.

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.

valves (licensed CC BY-NC-ND by thepismire)Arithmetic
The 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:
  1. 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.
  2. 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 GOTO and a loop label as target to do this.
This is a minimalist design. It has no else branch, nested conditionals or nested loops. It models the required control flow for Fizz Buzz:
'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 program
Because 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 symbolnewStatenewSymboldirection
(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' instructionhalt, stop the TM.
'l'/'r'instructionmove the cursor one number to the left or right.
'i' instructionincrement the current number by one and move cursor right.
'e' instructiondecrement the current number.
'd' instructionduplicate current number to the right.
'3' instructionwrite the digits of 3 into the current number.
'<' instructionjump to end of block if current is not < next number.
'=' instructionjump to end of block if current is not = next number.
'z' instructionjump to end of block if current number is not 0.
';' label mark the end of the (conditional) block.
'g' instructionjump backwards (moving 'P' left) until the label 'L'.
'L' label Loop label for goto (backwards) jump.

Apples in tarpits (licensed CC BY-NC-ND by Pay No Mind)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 - 1
I 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.

15 September 2025

Von Neumann Turing Machine

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.

MM Numbers (licensed CC BY-NC-ND by Michele C)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:
  1. Move the read/write head right until the end of the number (i.e. until the '$') to do the increment.
  2. Work backwards, i.e. move left to increment.
  3. If there is a '0', then write a '1' which finishes increment - and start moving right to the end.
  4. If there is a '1', then write a '0' and continue incrementing left with the overflow bit.
  5. 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 symbolnewStatenewSymboldirection
(1) Inc anyInc_MoveRightAndIncsameR
 Inc_MoveRightAndInc'0'Inc_MoveRightAndIncsameR
 Inc_MoveRightAndInc'1'Inc_MoveRightAndIncsameR
(2) Inc_MoveRightAndInc'$'Inc_IncToTheLeft sameL
(3) Inc_IncToTheLeft '0'Inc_DoneMoveRight '1' none
(4) Inc_IncToTheLeft '1'Inc_IncToTheLeft '0' L
(5) Inc_DoneMoveRight '0'Inc_DoneMoveRight sameR
 Inc_DoneMoveRight '1'Inc_DoneMoveRight sameR
(T) Inc_DoneMoveRight '$'Halt samenone

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 symbolnewState newSymboldirection
Dup '0'Dup_Move7RightAndWrite0 sameR
Dup_Move7RightAndWrite0anyDup_Move6RightAndWrite0 sameR
Dup_Move6RightAndWrite0anyDup_Move5RightAndWrite0 sameR
Dup_Move5RightAndWrite0anyDup_Move4RightAndWrite0 sameR
Dup_Move4RightAndWrite0anyDup_Move3RightAndWrite0 sameR
Dup_Move3RightAndWrite0anyDup_Move2RightAndWrite0 sameR
Dup_Move2RightAndWrite0anyDup_Move1RightAndWrite0 sameR
Dup_Move1RightAndWrite0anyDup_Write0AndMove7Back sameR
Dup_Write0AndMove7Back anyDup_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.

Dusty Bottle Neck (licensed CC BY-NC-ND by caramand)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
  1. Move the instruction pointer to the next instruction by switching the letter of the operation with 'P'.
  2. Move the read/write head right to the cursor 'C'. There replace the cursor with the separator '$'.
  3. Perform the operation. Each operation must end with the read/write head positioned at a separator.
  4. Set the new cursor position.
  5. Move the read/write head back to the instruction pointer
  6. 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 symbolnewState newSymboldirection
(1) Ip_SwitchRight 'i'Ip_SwitchLeftInc 'P' L
 Ip_SwitchLeftInc 'P'Code_Inc 'i' none
(2) Code_Inc 'C'Inc '$' R
 Code_Inc anysame sameR
(3) Inc anyInc_MoveRightAndIncsameR
 Inc_MoveRightAndInc'0'Inc_MoveRightAndIncsameR
 Inc_MoveRightAndInc'1'Inc_MoveRightAndIncsameR
 Inc_MoveRightAndInc'$'Inc_IncToTheLeft sameL
 Inc_IncToTheLeft '0'DoneMoveRight '1' none
 Inc_IncToTheLeft '1'Inc_IncToTheLeft '0' L
 DoneMoveRight '0'DoneMoveRight sameR
 DoneMoveRight '1'DoneMoveRight sameR
(4) DoneMoveRight '$'Ip_Restart 'C' none
(6) Ip_Restart 'P'Ip_SwitchRight sameR
(5) Ip_Restart anysame sameL

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.

5 August 2025

Universal Turing Machine

Turing Machine in Bletchley Park (licensed CC BY-NC-ND by Douglas Hoyt)The more I practice, the more I explore extreme situations. I have tried to go faster. Other times I Programmed with Nothing. Maybe it is the difficulty of only using low level constructs that makes this group of coding constraints appealing to me - which makes coding in assembly still interesting to some people, too. Then I tried to create Fizz Buzz using a Turing machine. I guess I lacked the purity of Computer Science university exercises. I will dive into Turing machines from a practical coding perspective using Java here.

Turing Machine
What is a Turing machine (TM)? First the TM is a though experiment. It was not meant to be practical. It is "the thing with the tape where a read-write head is able to read a zero or a one, write a zero or a one, erase the value, and move left or right." It is supposed to be Turing complete, which means it is equivalent to all programming languages today. That was my understanding of a TM when I started. But that understanding was impractical. Is a TM a program or a set of programs or a programming language? How can it be a specific program and Turing complete at the same time? And how could I implement anything like that?

Basic (Java) Building Blocks
First I need the building blocks. There is a set of symbols, maybe only 0 or 1 (a bit) or maybe a character to make things easier. So an empty marker interface Symbol should do. (The interface is optional, I like to make the symbol different from plain Object. I could use a char as well.) Then there is the tape which can be read and written to. The Tape class represents the tape as a data structure, such as an array or a list. Each cell of the tape holds a symbol.
class Tape<SYM extends Symbol> {

  private Map<Integer, SYM> cells = new TreeMap<>();
  private SYM defaultSymbol;
  private int headPosition = 0;

  Tape(List<SYM> symbols, SYM defaultValue) {
    for (int i = 0; i < symbols.size(); i++) {
      this.cells.put(i, symbols.get(i));
    }
    this.defaultSymbol = defaultValue;
  }

  SYM read() {
    return cells.getOrDefault(headPosition, defaultSymbol);
  }

  void write(SYM symbol) {
    cells.put(headPosition, symbol);
  }

  void moveHead(Direction direction) {
    switch (direction) {
    case LEFT:
      headPosition--;
      break;
    case NONE:
      break;
    case RIGHT:
      headPosition++;
      break;
    default:
      throw new IllegalArgumentException(direction.name());
    }
  }
}
The tape could be infinite, and I chose a Map for each symbol by its position. The default symbol is used for tape positions that have not been written to. The constructor accepts the initial content of the tape as the starting state of the machine. Now to the Turing machine:
class TuringMachine<SYM extends Symbol> {

  private Tape<SYM> tape;
  private State state;

  TuringMachine(Tape<SYM> tape, State initialState) {
    this.tape = tape;
    this.state = initialState;
  }

  private void setState(State state) {
    this.state = state;
  }

  private SYM read() {
    return tape.read();
  }

  private void write(SYM symbol) {
    tape.write(symbol);
  }

  private void move(Direction direction) {
    tape.moveHead(direction);
  }

  void loop() {
    while (!state.isTerminal()) {
      act();
    }
  }

  // ...
Following the description of a Turing machine, it has a state which can change. It can read the symbol currently present on the tape at the position of its read/write head. It can write a new symbol on the tape at the position of its read/write head, replacing the symbol that was previously there. And it can move its read/write head one position to the left or right along the tape. The machine runs as long as its state is not final. In each step (method act shown below) the machine reads the symbol present in the tape's cell, and based on the current state and the read symbol, it determines the next state and the symbol to write on the tape, then it moves the head left or right by one cell.
class TuringMachine<SYM extends Symbol> {

  // ...

  private void act() {
    SYM symbol = read();

    // transition to nextState determines
    // symbolToWrite and directionToMove

    setState(nextState);
    write(symbolToWrite);
    move(directionToMove);
  }

}
Of course this was not my initial code. I reached it by refactoring, cleaning up and structuring the code again and again. If this is a Turing machine, where is the actual program? The Tape and TuringMachine classes form a Universal Turing Machine (UTM). The UTM can simulate the behaviour of any Turing machine. It takes the description of an arbitrary Turing machine as input and mimics its operation on a given input string. Aha! My infrastructure can run an arbitrary Turing machine which makes each TM an individual program and the UTM the interpreter. Maybe I should have read the whole article on Wikipedia first.

Turing machine (licensed CC BY by Maria Keays)State Transitions
The actual program of a Turing machine is the set of its states and possible state transitions. It is a state machine, i.e. a graph of state nodes, and each edge between two states contains additional data: The Symbol symbolToWrite and the Direction directionToMove. In text, the easiest way to define this state machine is with a transition table of State state, Symbol symbol, State newState, Symbol newSymbol, Direction direction which is a TransitionTableRow in my TransitionTable implementation. (The whole transition logic is too much code to show here, the working solution is on my Git.) As I will create many transitions, I add defaults to the tables, e.g. state == null applies to all states, symbol == null applies to all symbols and newState == null or newSymbol == null does not change the current state or symbol. I want to avoid defining more table rows than strictly necessary.

A Simple Example
Now is the perfect time for an example. We want to set all bits of a binary number, e.g. 011010. The symbols are the bits 0 and 1 and a marker for the end of the input,
enum Bit implements Symbol {
  _0, _1, END_OF_TAPE
}
Starting at the left-most / highest bit. The transitions are
  • If the machine is running and the current bit is 0, then keep running, write a 1 and move right.
  • If the machine is running and the current bit is 1, then keep running, write a 1 and move right.
  • If the machine is running and the input has ended, then stop running (halt).
This is a simple machine and there are only two states: running and stopped,
enum S implements State {
  RUNNING, HALT;

  @Override
  public boolean isTerminal() { return this == HALT; }
}
and the whole things runs in this test,
class SimpleExampleTest {

  @Test
  void replaces0With1() {
    S initialState = S.RUNNING;
    var _011010 = Arrays.asList(_0, _1, _1, _0, _1, _0, END_OF_TAPE);
    var tape = new Tape<>(_011010, END_OF_TAPE);

    TransitionTable transitions = new TransitionTable().
        row(S.RUNNING, _0, null, _1, Direction.RIGHT).
        row(S.RUNNING, _1, null, null, Direction.RIGHT).
        row(S.RUNNING, END_OF_TAPE, S.HALT, null, Direction.NONE);

    var machine = new TuringMachine<>(tape, transitions, initialState);

    machine.loop();

    var expected_111111 = Arrays.asList(_1, _1, _1, _1, _1, _1, END_OF_TAPE);
    var actualResult = tape.getCells();
    assertEquals(expected_111111, actualResult);
  }
}
Now I know what a Turing machine is and how it is supposed to work. Using the Constructive Approach I created an UTM (TuringMachine.java) and an instance of a TM (in SimpleExampleTest.java). Now I can play around and see what is possible using only state transitions... I encourage you to do the same, clone my fizzbuzz-turing-machine repository and play around with the code in the universal package. This concludes the first part - the foundation if you like - of me implementing Fizz Buzz using a Turing machine. Continue with part 2.