Accepting GenAI

My Blacklist of Technologies
When I started out as a Java developer, I wanted to know everything about Java. I wanted to know all libraries and all frameworks. What a silly idea. Clearly Java or software development in general was and still is way too vast to know everything. Beginning 2003, I started ignoring certain technologies. I maintained a black list of topics and libraries, e.g. I decided to ignore all Java web frameworks. Later I ignored EJBs and then I added the whole Spring ecosystem to this list. While I knew these things existed and I had a working knowledge for my day job, I would refuse to study them in my personal free time. There was nothing wrong with these technologies. I did not find them interesting. Using that approach, I successfully skipped all the rage about SOA and other hypes, and I am not looking back. ;-) Explicitly ignoring topics helped me to focus on the things which I liked and considered important.

Scary or Awesome or What
And then ChatGPT came out. (The Wikipedia link is probably unnecessary.) There was an extreme buzz around it, and because of that I wanted to ignore it. A few months later I worked with a group of interns at one of my clients. These young people were enthusiastic about AI - most of them paid for pro versions from their own money - and they encouraged me to look into it. And so I did. And I got frightened. I enjoyed every post that diminished LLMs as stochastic parrots. Let's face it, isn't it weird when a machine can have a conversation with you? I am full of awe, also in a scared way - I am unsure what the right word is to describe my feeling.

Since last year, all of my clients ask for workshops to improve their coding with the use of AI. Code assistants and agents - augmented coding - get better and better. And sometimes the results are surprising. In the end, it is the same if AI works for coding or not - the industry has already decided on its adoption. For some time, I tried to deny it. But after Dave Farley's study about developers using AI, there was more denying it. I had to accept that AI will take over coding. (Dave Farley's video is 12 minutes, without hype, and in the end he gives a clear direction to follow. You should watch it.)

Fear of Obsolescence
Software development is changing quickly, and many of our skills become worthless (says Kent Beck). I read somewhere that "every technological revolution has displaced skills that people spent years mastering" and that "the people that are really skilled, have a lot of room to fall." (says Bryan Seegmiller). Yes, I feel like that. Coding is more than my work (and my fun), it is my identity. I have been playing with code since more than 40 years now. During this time, I have even established habits to use coding for relaxation, and I like exploring topics around code. I do not mean development, I particularly mean coding. I am the Code Cop and I am obsessed with manipulating the textual structure, improving its readability, exploring symmetries, tweaking it, moving it around like clay, and so on. And now all this is going away and it is scaring the hell out of me.

How am I dealing with all of this?
A senior developer from one of my clients, struggling with AI adoption himself, asked me how I am dealing with all of this? I am not, or at least not well. I thought about moving into areas where AI is useless and uncommon (yet?). For example, a study showed that AI is less effective on COBOL and other legacy code. Lovely! I bought a bunch of COBOL courses, and planned to take them. I had several other ideas, too, none of them really helped me till now. The core goal of this post was to list a few resources which really helped me:

• Maybe the first step is accepting the use of GenAI.
  
  
• I highly recommend this podcast with Grady Booch about the third golden age of software engineering. Grady Booch's approach is historical and more systemic. He is calm, with good perspective. It is 80 minutes long, audio-only is enough. This is the first piece that helped me to a more positive attitude.
  
  
• Kent Beck, who probably lost more to the rise of augmented coding than anybody, is lovely. In his conversation with Trisha Gee about Skills Developers Need to Have in an AI Future, they talk about developers losing confidence that they will be able to learn the next set of necessary skills. How true.
  
  
• Embrace Change is the second principle of the Agile Manifesto. While I try to stay clear of processes and am okay whether we use waterfall or Scrum or whatever, I do care about the code, and I favour Embracing Change there, designing in a way that would allow changes. Keeping software soft. Recently I was reminded of that fact by a fellow technical coach. So let's embrace change, even if it is frightening right now.
  
  
• Last month Kent Beck started a new podcast Still Burning where he has honest conversation about what it actually feels like to work in this moment - the fear, the uncertainty, the quiet disorientation of tools changing faster than understanding can follow.. The acknowledgement of these feelings, the disorientation, this is balm for my soul. I have always admired Kent Beck and the podcast setup is so grounded (actual fire, real smoke, Kent is coughing) and humble, it is already a classic.

What Next
These discussions helped me, and I hope they will help you, too. Am I done? I stay critical of using AI, its effects on me, my skills and the world in general. At the same time I try to board the AI train and follow along with the current. There are plenty opportunities to participate in AI experiments right now. Hopefully that will be enough to stay on the topic. My fear of missing out is real, I spend too much time with Generative AI. My wife already urges me to take a break from all this. It is exhausting. Everywhere it is just "AI", "AI", "AI".

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.

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	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

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	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.

Universal Turing Machine

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.

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 GitHub.) 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. Part two is here.