216Book Review: Good Math

Author: Dr. Heinz M. KabutzDate: 2013-12-30Java Version: 7Category: Book Review

Abstract: Software engineers need to have a good understanding of mathematics. In this newsletter, we review a book written by a geek and aimed at the geek who wants to discover interesting facts about maths.

Welcome to the 216th issue of The Java(tm) Specialists' Newsletter. Tomorrow my three oldest kids and I are planning a trip to go play in the snow. Yes, I am on Crete and yes, it gets cold here too, especially up on the mountains. Let's see if we get lucky! All the best for 2014 :-)

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Book Review: Good Math [ISBN 1937785335]

Before we start looking at the book, I have a section from my personal life that will hopefully motivate why I think this book is important for Java programmers to read. The book does not mention Java once, so why should you care? Well, it will show you how much you don't know, or maybe that you actually are pretty clever already. Feel free to skip over the personal section below if you are low on time, but you might find it an entertaining read nevertheless.

Heinz Is Not a Real Kabutz - He Can't Do Maths!

In my first year of elementary school, I managed to dazzle my teachers with my lack of mathematics aptitude. This was in the late 70s, and schools decided to experiment on us youngster and were teaching set theory to six year olds. I was hopelessly lost! The year before they had used colourful blocks to teach addition, so my older brothers learned that green plus blue is red, or similar nonsense. We then proceeded to doing word sums, such as "John has three apples, he cuts them in half, then again in half, then eats one third and feeds one half to his goat. Does John have haemorrhoids?" Or something to that effect. Again, I was hopelessly lost. I found out years later that my teachers had discussed sending me to a "special" school, and not the gifted kind.

Over time, I improved a bit. I was in the top three in my class, but had a very strange style of answering tests. Even as a youngster, I worked well under pressure. Tests used to be written over two periods of 45 minutes each. I would answer about 10% of my paper in the first period and the rest in the second period, when I was under a lot of pressure. This worked well until my teacher decided one day to give us only a single period for the test. Before I knew it, we had five minutes left and I had only answered about 10% of the paper. I tried my best, but it was hopeless. I failed dismally.

As a child, I enjoyed maths puzzles and even won a prize in 5th grade for answering a maths competition at school. My answer was completely wrong, but since I was the only one who had bothered handing in an answer they gave me the prize. Maths problems fascinated me and so I joined an early morning advanced maths class in elementary school, where, amongst other things, we learned how to manually calculate the square root of a number. It was at the same time that I began programming ZX Basic, where maths was actually had a practical use.

People have often asked me whether they should pursue a career as a computer programmer. They see my lifestyle, living on an island in a beautiful home and without dirt under the fingernails. I tell them that programming really is not all that difficult, but that typically the types of people that enjoy it are also pretty good at maths. Of course there are exceptions to the rule, but an enquiring mind and an aptitude for problem solving, help a lot in our career. Thus my first question to them is usually: "How did you do at maths?" If they really did not like maths, then they will probably have difficulty understanding the Turing Machine.

During high school my maths ability started to develop a bit. I never got the class prize, but that was because I was just too inconsistent. I would write top marks several times, followed by a complete crash due to bad time keeping or simple carelessness. One time, I thought we were writing our geography exam, when actually we were writing maths! I had almost no time to prepare myself, but still did remarkably well, considering. I'm your quintessential nutty professor. When I cannot find an item at home, I force myself to not accuse my family, because 95% of the time, I mislaid it myself. This carelessness used to drive my teachers nuts. Fortunately in programming we have unit tests and compilers to catch our mistakes.

The University of Cape Town had maths olympiads for school children. I used to not go, because I was scared of failure. However, eventually I mustered the courage and came 11th in Cape Town, a city of 3.5 million with lots of school children. The first 10 were recognized and went through to the next round, so unfortunately I missed that. I also wrote a national maths olympiad in grade 12. I was sitting in the first row of the room, near my friend Steven. Since this exam did not count for marks, the kids behind us started cheating and passing around their answers. Somehow Steven and I got wind of this, although the teacher remained oblivious. We wanted to join in, but due to where we were sitting, were excluded from the cheat gang. Amusingly, I was the only one from my class who went through to round two. It would have been funny if the gang behind us had all passed. Second round was a disaster though and I got a glimpse of what real maths was all about!

At one point, I was so confident I was the next maths genius, that I considered a career in actuarial science. However, my guidance counselor talked me out of it and suggested rather a career in computer science. When I arrived at the University of Cape Town, which is the top university on the continent of Africa, famous for many research breakthroughs and, more importantly, situated on one of the most beautiful settings in the most stunning city in the world, I enlisted in an advanced first-year maths course, MTH106W. There were only 15 students in the class. It was insanely difficult. In the previous year, half the class had failed. Our year was the last that they did it in that format, because even top maths students struggled. And would you believe it, we started with my old nemesis, set theory! We learned about limits, about infinity. We learned what "onto" meant and how to use it to prove that the set of even numbers is the same size as the set of all natural numbers. Most of the time, I was lost. It did not help that our professor had an almost incomprehensible Russian accent, nor that our teaching assistant was a genius who wrote his PhD in 9 months. I was so so lost. By some miracle I managed to pass, but I finally understood that whilst I wasn't too bad at maths, I certainly wasn't mathematician material.

The Good Math [ISBN 1937785335] Book

If you are looking for a book to keep you entertained during the festive season, Good Math [ISBN 1937785335] is the one you want. It is full of interesting geek facts about numbers and mathematics. And, you guessed it, it again contained set theory and a bunch of things that I still cannot grasp. But it also has many other topics that I learned about at the University of Cape Town, but which I had mostly put into long-term storage in my brain.

One of the particularly interesting sections was on continued fractions. Since the author Mark Chu-Carroll is a mathematician, he seems to prefer languages like Haskell and Scala. However, I decided to code a bit myself in Java. A continued fraction allows us to describe rational and irrational numbers with greater accuracy. They take the form of 1 + 1 / (n + 1 / (m + 1 / ... )). For example, the mystical number phi is irrational, but can be expressed as a continued fraction with 1 + 1 / (1 + 1 / (1 + 1 / (1 + 1 / (1 + ... )))). Obviously, writing continued fractions like that is cumbersome, so instead we can use the notation [1; 1, 1, 1, 1, 1, ...]. We can also use it to represent rational numbers, thus 2.3456 could be written as [2; 2, 1, 8, 2, 1, 1, 4].

Here is some code that I wrote to demonstrate how we can do the calculation in Java. In the book there is an alternate approach using Scala. An interesting property of the continued fraction is that the inverse is simply a shift to the right or left of the digits. You can see this in the inverse() method below. I also have two methods for calculating the number, one which returns a double and the other a BigDecimal, taking the scale of the number as argument.

import java.math.*;
import java.util.*;

public class ContinuedFraction {
  private final int first;
  private final int[] remain;

  public ContinuedFraction(int first, int... remain) {
    this.first = first;
    this.remain = remain;
  }

  public double doubleValue() {
    double result = first;
    double factor = 0;
    for (int i = remain.length - 1; i >= 0; i--) {
      factor = 1.0 / (factor + remain[i]);
    }
    return factor + first;
  }

  public BigDecimal calculate(int scale) {
    BigDecimal result = new BigDecimal(first);
    BigDecimal factor = BigDecimal.ZERO;
    for (int i = remain.length - 1; i >= 0; i--) {
      factor = BigDecimal.ONE.divide(factor.add(
          new BigDecimal(remain[i])), scale,
          RoundingMode.HALF_EVEN);
    }
    return factor.add(new BigDecimal(first));
  }

  public ContinuedFraction inverse() {
    if (first == 0) {
      return new ContinuedFraction(remain[0],
          Arrays.copyOfRange(remain, 1, remain.length));
    } else {
      int[] newRemain = new int[remain.length + 1];
      newRemain[0] = first;
      System.arraycopy(remain, 0, newRemain, 1, remain.length);
      return new ContinuedFraction(0, newRemain);
    }
  }
}

As you can see here, we can produce the continued fraction of rational numbers (such as 2.3456) but also of irrational, such as Phi. In our example, we calculate Phi to 100 decimal places by constructing an array of 250 ones for the remaining digits. We also show how we can calculate Pi to 9 digits by simply using 5 remaining digits [3; 7, 15, 1, 292, 1]. Powerful stuff!

import javax.xml.transform.*;
import java.math.*;
import java.util.*;

public class ContinuedFractionTest {
  public static void main(String... args) {
    ContinuedFraction cf1 = // 2.3456
        new ContinuedFraction(2, 2, 1, 8, 2, 1, 1, 4);
    System.out.println(cf1.doubleValue());
    System.out.println(cf1.inverse().doubleValue());
    System.out.println(1.0 / 2.3456);


    int[] ones = new int[250];
    Arrays.fill(ones, 1);
    ContinuedFraction phi = new ContinuedFraction(1, ones);
    System.out.println(phi.calculate(100));
    System.out.println("1.6180339887498948482045868343656381" +
        "177203091798057628621354486227052604628189024497072" +
        "07204189391137484754");

    ContinuedFraction pi = new ContinuedFraction(
        3, 7, 15, 1, 292, 1
    );
    System.out.println(pi.calculate(9));
    System.out.println("3.141592653589");
    System.out.println(Math.PI);
  }
}

2.3456
0.4263301500682128
0.4263301500682128
1.61803398874989484820458683436563811772030917980576286213544\
    86227052604628189024497072072041893911375
1.61803398874989484820458683436563811772030917980576286213544\
    8622705260462818902449707207204189391137484754
3.141592654
3.141592653589
3.141592653589793

Egyptian Fractions

Another fascinating chapter was on Egyptian Fractions. The fraction 2/3 was considered "vulgar", because it had a non-one nominator. Thus instead of saying 2/3, in Ancient Egypt, you would say 1/2 + 1/6. You can still hear the effect of this custom in Greece when telling someone the time. You say either 1/4 before eight or 1/4 after eight. You never say 3/4 after seven. As you can imagine, converting vulgar fractions to Egyptian Fractions could be quite cumbersome. Fibonacci devised a method to calculate this in a finite amount of time, but not necessarily in the most efficient representation.

In order to demonstrate this, I wrote a Fraction class. When we construct it, it finds the greatest common denominator (gcd) between the numerator and denominator and simplifies the fraction. Thus if we construct 5/10, it changes it to 1/2. We can also generate Egyptian Fractions using Fibonacci's greedy algorithm that states e(x/y) = 1/ceil(y/x) + e(r), where r = (-y mod x) / (y * ceil(y/x)).

import java.math.*;
import java.util.*;

public final class Fraction {
  private final BigInteger num;
  private final BigInteger den;

  public Fraction(BigInteger num, BigInteger den) {
    if (den.equals(BigInteger.ZERO)) {
      throw new ArithmeticException("divide by zero");
    }
    BigInteger gcd = gcd(num, den);
    this.num = num.divide(gcd);
    this.den = den.divide(gcd);
  }

  private BigInteger gcd(BigInteger a, BigInteger b) {
    if (b.equals(BigInteger.ZERO)) return a;
    return gcd(b, a.mod(b));
  }

  public Fraction(String num, String den) {
    this(new BigInteger(num), new BigInteger(den));
  }

  public Fraction(long num, long den) {
    this(Long.toString(num), Long.toString(den));
  }

  public Fraction add(Fraction other) {
    BigInteger newDen = other.den.multiply(den);
    BigInteger newNum = num.multiply(other.den).add(
        other.num.multiply(den)
    );
    return new Fraction(newNum, newDen);
  }

  public static Fraction addAll(Fraction... fractions) {
    Fraction total = new Fraction(0, 1);
    for (Fraction fraction : fractions) {
      total = total.add(fraction);
    }
    return total;
  }

  public Fraction[] getEgyptianFractions() {
    Collection<Fraction> fractions = new ArrayList<>();
    findEgyptianFractions(fractions, num, den);
    return fractions.toArray(new Fraction[fractions.size()]);
  }

  private static void findEgyptianFractions(
      Collection<Fraction> result,
      BigInteger x, BigInteger y) {
    if (x.equals(BigInteger.ZERO)) {
      return;
    }
    BigInteger den = y.divide(x).add(
        (y.mod(x).equals(BigInteger.ZERO)
            ? BigInteger.ZERO : BigInteger.ONE));
    result.add(new Fraction(BigInteger.ONE, den));
    BigInteger remx = y.negate().mod(x);
    BigInteger remy = y.multiply(den);
    findEgyptianFractions(result, remx, remy);
  }

  public String toString() {
    return num + "/" + den;
  }

  public boolean equals(Object o) {
    if (!(o instanceof Fraction)) return false;
    Fraction fraction = (Fraction) o;
    return den.equals(fraction.den) &&
        num.equals(fraction.num);
  }

  public int hashCode() {
    return (num.hashCode() << 16) ^ den.hashCode();
  }
}

Here are some sample vulgar fractions, with their Egyptian Fraction generated by the function getEgyptianFractions(). Once printed, I total them to make sure that they equal the original fraction. Remember what I worte earlier about how careless I am.

public class FibonacciEgyptianFractions {
  public static void main(String... args) {
    test(1, 3);
    test(2, 3);
    test(3, 4);
    test(4, 5);
    test(9, 31);
    test(21, 50);
    test(1023, 1024);
    test(5, 121);
  }

  private static void test(long num, long den) {
    Fraction fraction = new Fraction(num, den);
    System.out.print(fraction + " = ");
    Fraction[] fs = fraction.getEgyptianFractions();
    for (int i = 0; i < fs.length; i++) {
      System.out.print(fs[i]);
      if (i < fs.length - 1) System.out.print(" + ");
    }
    System.out.print(" = ");
    Fraction total = new Fraction(0, 1);
    for (Fraction f : fs) {
      total = total.add(f);
    }
    System.out.println(total);
  }
}

1/3 = 1/3 = 1/3
2/3 = 1/2 + 1/6 = 2/3
3/4 = 1/2 + 1/4 = 3/4
4/5 = 1/2 + 1/4 + 1/20 = 4/5
9/31 = 1/4 + 1/25 + 1/3100 = 9/31
21/50 = 1/3 + 1/12 + 1/300 = 21/50
1023/1024 = 1/2 + 1/3 + 1/7 + 1/44 + 1/9462
            + 1/373029888 = 1023/1024
5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913
        + 1/1527612795642093418846225 = 5/121

Logic Programming

After laying the foundations of logical arguments, we take a stab at logical programming with Prolog. In his book, Chu-Carroll states that if there is one language that you should learn in addition to the ones you know already, it is Prolog. This is quite a big statement, but I tend to agree with him. Here is what you can do with it. I define a bunch of persons:

person(heinz).
person(helene).
person(efi).
person(hans).
person(rudolf).
person(thomas).
person(maike).
father(hans,heinz).
father(hans,rudolf).
father(heinz,efi).
father(rudolf,thomas).
father(rudolf,maike).
mother(helene,efi).

I then define the parent() and grandparent() relations:

parent(X,Y) :- father(X,Y); mother(X,Y).
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).

Once we have defined the parent, we can define sibling as having one of the same parent:

sibling(X,Y) :-
  X \= Y,
  parent(P,X),
  parent(P,Y).

And a cousin is someone whose parent is a sibling of our parent:

cousin(X,Y) :-
  parent(P,X),
  parent(Q,Y),
  sibling(P,Q).

We can now query the family tree to see whether two people are cousins, for example:

?- cousin(efi,maike).
true .

?- cousin(efi,thomas).
true .

?- cousin(maike,thomas).
false .

?- cousin(efi,X).
X = thomas ;
X = maike ;
false.

In the book, we see an example of quicksort using Prolog. Lots of fun! And it even works!

Turing Machine

The book then carries on for a while about sets and infinity. My brain does not function well enough for those topics. It didn't when I was six years old and in grade one, neither did it when I was 18 and in first year of university and it still doesn't, now that I am 42. Perhaps when I'm retired I will have an epiphany. But then the book stopped that nonsense and went to mechanical computing, which is more in line with what we commonly do.

One of my favourite constructs is the Turing Machine, named after the famous Alan Turing, who was recently pardoned by the Queen. I showed the diagram to my twelve year old, who could not believe how simple it was. A finite set of states, a finite set of symbols that can be written, and, here's the catch, an infinite amount of tape to read from and write to. In every state, the current symbol is read and depending on what it is, we write a symbol back (possibly the same one). We then move either right or left and change state. That's it, really.

The beauty is in its simplicity, which also allows us to prove a bunch of things about it. For example, in the book, they mention that someone proved in 2007 that you can construct a two-state, three-symbol Universal Turing Machine that can be used to generate all other Universal Turing Machines. Since this was a while after I left academia, I did some digging and found this amazing turing machine, first proposed by Wolfram and then proved to be turing complete.

One thing I've always wanted to do is write a Turing Machine in Java. Obviously it would not have an infinite amount of tape. If we use a StringBuilder for tape, then we are limited by the array size in Java. Even the finite alphabet could pose a problem, because finite can still be very large. For example 10 to the power of 10000 is finite. In the book, they write a simple algorithm for subtracting numbers in unary notation, where decimal 4 would be written as 1111. Thus 1111111111-1111111=111, or 10-7=3 in decimal. They even defined a simple language for setting up the machine, where the algorithm was defined as:

states { "scan" "erase1" "subtract1" "skip" } initial "scan"
alphabet { '1' ' ' '=' '-' } blank ' '
trans from "scan" to "scan" on (' ') write ' ' move right
trans from "scan" to "scan" on ('1') write '1' move right
trans from "scan" to "scan" on ('-') write '-' move right
trans from "scan" to "erase1" on ('=') write ' ' move left
trans from "erase1" to "subtract1" on ('1') write '=' move left
trans from "erase1" to "Halt" on ('-') write ' ' move left
trans from "subtract1" to "subtract1" on ('1') write '1' move left
trans from "subtract1" to "skip" on ('-') write '-' move left
trans from "skip" to "skip" on (' ') write ' ' move left
trans from "skip" to "scan" on ('1') write ' ' move right

In my Turing Machine, we construct it with the create(String) method, which parses the lines and creates the states, symbols and transitions. We can then execute it with a tape of symbols and watch the progress as the head moves back and forth on the tape.

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class TuringMachine {
  private static final Pattern statesPattern = Pattern.compile(
      "states \\{ (.*) \\} initial \"(\\w+)\""
  );

  private static final Pattern alphabetPattern = Pattern.compile(
      "alphabet \\{ *(.*) *\\} blank '(.)'"
  );

  private static final Pattern transPattern = Pattern.compile(
      "trans from \"(.*)\" to \"(.*)\" on \\('(.)'\\) " +
          "write '(.)' move (right|left)"
  );

  private static final State HALT = new State("Halt");

  private static class State {
    private final String name;
    private final Map<Character, Transition> transitions =
        new HashMap<>();

    State(String name) {
      this.name = name;
    }

    public String toString() {
      return name;
    }

    public void addTransition(Transition transition) {
      if (transition.from != this) {
        throw new IllegalArgumentException();
      }
      transitions.put(transition.read, transition);
    }

    public Transition getTransition(char read) {
      return transitions.get(read);
    }
  }

  private static enum Move {
    left, right;
  }

  private static class Transition {
    private final State from, to;
    private final char read;
    private final char write;
    private final Move move;

    Transition(State from, State to, char read, char write,
               Move move) {
      this.from = from;
      this.to = to;
      if (this.from == null) throw new NullPointerException();
      if (this.to == null) throw new NullPointerException();
      this.read = read;
      this.write = write;
      this.move = move;
    }

    public String toString() {
      return "trans from \"" + from + "\" to \"" + to + "\" " +
          "on ('" + read + "') write '" + write + "' " +
          "move " + move;
    }
  }

  private final State initial;
  private final char blank;

  private TuringMachine(State initial, char blank) {
    this.initial = initial;
    this.blank = blank;
  }

  public CharSequence execute(CharSequence input) {
    State state = initial;
    StringBuilder tape = new StringBuilder(input);
    int pos = 0;
    while (state != HALT) {
      System.out.println(">>> " + tape);
      System.out.println(space(pos + 4) + "^" +
          space(Math.max(50 - pos, 10)) + state);

      char read = tape.charAt(pos);
      Transition transition = state.getTransition(read);
      if (transition == null) {
        throw new IllegalStateException(
            "No valid transition defined for state " + state +
                " and symbol '" + read + "'");
      }
      tape.setCharAt(pos, transition.write);
      if (transition.move == Move.left) {
        if (pos == 0) {
          tape.insert(0, blank);
        } else {
          pos--;
        }
      } else {
        pos++;
        if (pos >= tape.length()) {
          tape.append(blank);
        }
      }
      state = transition.to;
    }
    return tape;
  }

  private String space(int length) {
    char[] spaces = new char[length];
    Arrays.fill(spaces, ' ');
    return new String(spaces);
  }

  public static TuringMachine create(String program)
      throws IOException {
    BufferedReader in = new BufferedReader(
        new StringReader(program)
    );
    String line;
    Map<String, State> states = new HashMap<>();
    states.put("Halt", HALT);
    State initial = null;
    Character blank = null;
    Set<Character> alphabet = new LinkedHashSet<>();

    while ((line = in.readLine()) != null) {
      Matcher matcher = statesPattern.matcher(line);
      if (matcher.matches()) {
        String[] stateStrings = matcher.group(1).replaceAll(
            "\"", "").split(" ");
        String initialString = matcher.group(2);
        for (String s : stateStrings) {
          State state = new State(s);
          states.put(s, state);
        }
        initial = states.get(initialString);
        continue;
      }
      matcher = alphabetPattern.matcher(line);
      if (matcher.matches()) {
        String chars = matcher.group(1);
        boolean openingquoteseen = false;
        for (int i = 0; i < chars.length(); i++) {
          if (openingquoteseen) {
            alphabet.add(chars.charAt(i));
            openingquoteseen = false;
            i++;
          } else if (chars.charAt(i) == '\'') {
            openingquoteseen = true;
          } else {
            // skip.
          }
        }
        blank = matcher.group(2).charAt(0);
        continue;
      }
      matcher = transPattern.matcher(line);
      if (matcher.matches()) {
        State from = states.get(matcher.group(1));
        if (from == null) {
          throw new IllegalArgumentException(
              "undefined state \"" + matcher.group(1) + "\"");
        }
        State to = states.get(matcher.group(2));
        if (to == null) {
          throw new IllegalArgumentException(
              "undefined state \"" + matcher.group(2) + "\"");
        }
        char read = matcher.group(3).charAt(0);
        if (!alphabet.contains(read)) {
          throw new IllegalArgumentException(
              "alphabet does not contain '" + read + "'");
        }
        char write = matcher.group(4).charAt(0);
        if (!alphabet.contains(write)) {
          throw new IllegalArgumentException(
              "alphabet does not contain '" + write + "'");
        }
        String move = matcher.group(5);
        Transition transition = new Transition(from, to,
            read, write, Move.valueOf(move));
        from.addTransition(transition);
        continue;
      }
      if (!line.isEmpty() && !line.startsWith("\\s*//")) {
        throw new IllegalStateException(
            "Unrecognized line: " + line);
      }
    }
    return new TuringMachine(initial, blank);
  }
}

The code is a bit messy, as I've been writing it on the family couch whilst watching the baby attempting to crawl. The parsing would be better done with a proper parser than with my weak regular expressions. However, it does seem to work well enough, and besides, you could always use my Turing Machine to design another Turing Machine that can generate better code :-) Here is the code for subtracting unary numbers:

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class TuringMachineSubtract {
  public static void main(String... args) throws IOException {
    String program = "" +
        "states { \"scan\" \"erase1\" \"subtract1\" \"skip\" }" +
        " initial \"scan\"\n" +
        "alphabet { '1' ' ' '=' '-' } blank ' '\n" +
        "trans from \"scan\" to \"scan\" on (' ') write ' '" +
        " move right\n" +
        "trans from \"scan\" to \"scan\" on ('1') write '1'" +
        " move right\n" +
        "trans from \"scan\" to \"scan\" on ('-') write '-'" +
        " move right\n" +
        "trans from \"scan\" to \"erase1\" on ('=') write ' '" +
        " move left\n" +
        "trans from \"erase1\" to \"subtract1\" on ('1') write" +
        " '=' move left\n" +
        "trans from \"erase1\" to \"Halt\" on ('-') write ' '" +
        " move left\n" +
        "trans from \"subtract1\" to \"subtract1\" on ('1')" +
        " write '1' move left\n" +
        "trans from \"subtract1\" to \"skip\" on ('-')" +
        " write '-' move left\n" +
        "trans from \"skip\" to \"skip\" on (' ') write ' '" +
        " move left\n" +
        "trans from \"skip\" to \"scan\" on ('1') write ' '" +
        " move right\n";
    System.out.println(program);

    TuringMachine tm = TuringMachine.create(program);
    test(tm, "11111111-11111=");
    test(tm, "1111111-11111=");
    test(tm, "11111-11111=");
    test(tm, "11111-11=");
    test(tm, "11111-1=");
  }

  private static void test(TuringMachine tm, CharSequence input) {
    System.out.println(input + " => " + tm.execute(input));
  }
}

For example, here is 11111-11= executed on our Turing Machine:

>>> 11111-11=
    ^                                                  scan
>>> 11111-11=
     ^                                                 scan
>>> 11111-11=
      ^                                                scan
>>> 11111-11=
       ^                                               scan
>>> 11111-11=
        ^                                              scan
>>> 11111-11=
         ^                                             scan
>>> 11111-11=
          ^                                            scan
>>> 11111-11=
           ^                                           scan
>>> 11111-11=
            ^                                          scan
>>> 11111-11 
           ^                                           erase1
>>> 11111-1= 
          ^                                            subtract1
>>> 11111-1= 
         ^                                             subtract1
>>> 11111-1= 
        ^                                              skip
>>> 1111 -1= 
         ^                                             scan
>>> 1111 -1= 
          ^                                            scan
>>> 1111 -1= 
           ^                                           scan
>>> 1111 -1  
          ^                                            erase1
>>> 1111 -=  
         ^                                             subtract1
>>> 1111 -=  
        ^                                              skip
>>> 1111 -=  
       ^                                               skip
>>> 111  -=  
        ^                                              scan
>>> 111  -=  
         ^                                             scan
>>> 111  -=  
          ^                                            scan
>>> 111  -   
         ^                                             erase1
11111-11= => 111      

I wrote my own little unary add Turing Machine code, which looks like this:

import java.io.*;

public class TuringMachineAdd {
  public static void main(String... args) throws IOException {
    String program = "" +
        "states { \"scan\" \"erase1\" \"add\" \"clean\" }" +
        " initial \"scan\"\n" +
        "alphabet { '1' ' ' '=' '+' } blank ' '\n" +
        "trans from \"scan\" to \"scan\" on (' ') write ' '" +
        " move right\n" +
        "trans from \"scan\" to \"scan\" on ('1') write '1'" +
        " move right\n" +
        "trans from \"scan\" to \"add\" on ('+') write '+'" +
        " move right\n" +
        "trans from \"add\" to \"erase1\" on ('1') write '+'" +
        " move left\n" +
        "trans from \"add\" to \"clean\" on ('=') write ' '" +
        " move left\n" +
        "trans from \"clean\" to \"Halt\" on ('+') write ' '" +
        " move left\n" +
        "trans from \"erase1\" to \"scan\" on ('+') write '1'" +
        " move right\n";
    System.out.println(program);

    TuringMachine tm = TuringMachine.create(program);
    test(tm, "11111111+11111=");
    test(tm, "1111111+11111=");
    test(tm, "11111+11111=");
    test(tm, "11111+11=");
    test(tm, "111+11=");
    test(tm, "1+1=");
  }

  private static void test(TuringMachine tm, CharSequence input) {
    System.out.println(input + " => " + tm.execute(input));
  }
}

For example, 111+11= can be seen executing below:

states { "scan" "erase1" "add" "clean" } initial "scan"
alphabet { '1' ' ' '=' '+' } blank ' '
trans from "scan" to "scan" on (' ') write ' ' move right
trans from "scan" to "scan" on ('1') write '1' move right
trans from "scan" to "add" on ('+') write '+' move right
trans from "add" to "erase1" on ('1') write '+' move left
trans from "add" to "clean" on ('=') write ' ' move left
trans from "clean" to "Halt" on ('+') write ' ' move left
trans from "erase1" to "scan" on ('+') write '1' move right

>>> 111+11=
    ^                                                  scan
>>> 111+11=
     ^                                                 scan
>>> 111+11=
      ^                                                scan
>>> 111+11=
       ^                                               scan
>>> 111+11=
        ^                                              add
>>> 111++1=
       ^                                               erase1
>>> 1111+1=
        ^                                              scan
>>> 1111+1=
         ^                                             add
>>> 1111++=
        ^                                              erase1
>>> 11111+=
         ^                                             scan
>>> 11111+=
          ^                                            add
>>> 11111+ 
         ^                                             clean
111+11= => 11111  

In the book Good Math [ISBN 1937785335] , they mention the story that we have a Turing Machine that can define is turing complete, meaning that it could be used to define any other Turing Machine. I did some research and found this amazing Turing Machine. States are A and B. Alphabet is 0, 1 and 2. It does not have a Halt state.

import java.io.*;

public class TuringMachineUniversal {
  public static void main(String... args) throws IOException {
    String program = "" +
        "states { \"A\" \"B\" } initial \"A\"\n" +
        "alphabet { '0' '1' '2' } blank '0'\n" +
        "trans from \"A\" to \"B\" on ('0') write '1'" +
        " move right\n" +
        "trans from \"A\" to \"A\" on ('1') write '2'" +
        " move left\n" +
        "trans from \"A\" to \"A\" on ('2') write '1'" +
        " move left\n" +
        "trans from \"B\" to \"A\" on ('0') write '2'" +
        " move left\n" +
        "trans from \"B\" to \"B\" on ('1') write '2'" +
        " move right\n" +
        "trans from \"B\" to \"A\" on ('2') write '0'" +
        " move right\n" +
        "";
    System.out.println(program);

    TuringMachine tm = TuringMachine.create(program);
    test(tm, "012012");
  }

  private static void test(TuringMachine tm, CharSequence input) {
    System.out.println(input + " => " + tm.execute(input));
  }
}

Since there is no Halt state, this will keep on running until we run out of memory on our tape. Here are the first few lines of output for Wolfram's machine:

states { "A" "B" } initial "A"
alphabet { '0' '1' '2' } blank '0'
trans from "A" to "B" on ('0') write '1' move right
trans from "A" to "A" on ('1') write '2' move left
trans from "A" to "A" on ('2') write '1' move left
trans from "B" to "A" on ('0') write '2' move left
trans from "B" to "B" on ('1') write '2' move right
trans from "B" to "A" on ('2') write '0' move right

>>> 012012
    ^                                                  A
>>> 112012
     ^                                                 B
>>> 122012
      ^                                                B
>>> 120012
       ^                                               A
>>> 120112
        ^                                              B
>>> 120122
         ^                                             B
>>> 1201200
          ^                                            A
>>> 12012010
           ^                                           B
>>> 12012012
          ^                                            A
>>> 12012022
         ^                                             A

Overall, I like this book very much, not just for what I learned from it, but by showing me how little I understand about the intricacies of set theory, groups, etc. It has nothing to do with Java per se, but it is a good book for a software engineer to read. You might discover that you aren't quite as clever as you've always thought ;-)

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive