The Java Specialists' Newsletter

Issue 2162013-12-30
Category:
Book Review
Java version: Java 7

Subscribe
RSS Feed

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

**NEW: Refactoring to Java 8 Lambdas and Streams Workshop**
Are you currently using Java 6 or 7 and would like to see how
Java 8 can improve your code base? Are you tired of courses
that teach you a whole bunch of techniques that you cannot
apply in your world? Check out our one day intensive
Refactoring to Java 8 Lambdas and Streams Workshop.

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.

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.

If you are looking for a book to keep you entertained during the festive season, Good Math 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.

importjava.math.*;importjava.util.*;publicclassContinuedFraction {privatefinalintfirst;privatefinalint[] remain;publicContinuedFraction(intfirst,int... remain) {this.first = first;this.remain = remain; }publicdoubledoubleValue() {doubleresult = first;doublefactor = 0;for(inti = remain.length - 1; i >= 0; i--) { factor = 1.0 / (factor + remain[i]); }returnfactor + first; }publicBigDecimal calculate(intscale) { BigDecimal result =newBigDecimal(first); BigDecimal factor = BigDecimal.ZERO;for(inti = remain.length - 1; i >= 0; i--) { factor = BigDecimal.ONE.divide(factor.add(newBigDecimal(remain[i])), scale, RoundingMode.HALF_EVEN); }returnfactor.add(newBigDecimal(first)); }publicContinuedFraction inverse() {if(first == 0) {returnnewContinuedFraction(remain[0], Arrays.copyOfRange(remain, 1, remain.length)); }else{int[] newRemain =newint[remain.length + 1]; newRemain[0] = first; System.arraycopy(remain, 0, newRemain, 1, remain.length);returnnewContinuedFraction(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!

importjavax.xml.transform.*;importjava.math.*;importjava.util.*;publicclassContinuedFractionTest {publicstaticvoidmain(String... args) { ContinuedFraction cf1 = // 2.3456newContinuedFraction(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 =newint[250]; Arrays.fill(ones, 1); ContinuedFraction phi =newContinuedFraction(1, ones); System.out.println(phi.calculate(100)); System.out.println("1.6180339887498948482045868343656381"+"177203091798057628621354486227052604628189024497072"+"07204189391137484754"); ContinuedFraction pi =newContinuedFraction( 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

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

importjava.math.*;importjava.util.*;publicfinalclassFraction {privatefinalBigInteger num;privatefinalBigInteger den;publicFraction(BigInteger num, BigInteger den) {if(den.equals(BigInteger.ZERO)) {thrownewArithmeticException("divide by zero"); } BigInteger gcd = gcd(num, den);this.num = num.divide(gcd);this.den = den.divide(gcd); }privateBigInteger gcd(BigInteger a, BigInteger b) {if(b.equals(BigInteger.ZERO))returna;returngcd(b, a.mod(b)); }publicFraction(String num, String den) {this(newBigInteger(num),newBigInteger(den)); }publicFraction(longnum,longden) {this(Long.toString(num), Long.toString(den)); }publicFraction add(Fraction other) { BigInteger newDen = other.den.multiply(den); BigInteger newNum = num.multiply(other.den).add( other.num.multiply(den) );returnnewFraction(newNum, newDen); }publicstaticFraction addAll(Fraction... fractions) { Fraction total =newFraction(0, 1);for(Fraction fraction : fractions) { total = total.add(fraction); }returntotal; }publicFraction[] getEgyptianFractions() { Collection<Fraction> fractions =newArrayList<>(); findEgyptianFractions(fractions, num, den);returnfractions.toArray(new Fraction[fractions.size()]); }privatestaticvoidfindEgyptianFractions( 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(newFraction(BigInteger.ONE, den)); BigInteger remx = y.negate().mod(x); BigInteger remy = y.multiply(den); findEgyptianFractions(result, remx, remy); }publicString toString() {returnnum +"/"+ den; }publicbooleanequals(Object o) {if(!(o instanceof Fraction))returnfalse; Fraction fraction = (Fraction) o;returnden.equals(fraction.den) && num.equals(fraction.num); }publicinthashCode() {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.

publicclassFibonacciEgyptianFractions {publicstaticvoidmain(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); }privatestaticvoidtest(longnum,longden) { Fraction fraction =newFraction(num, den); System.out.print(fraction +" = "); Fraction[] fs = fraction.getEgyptianFractions();for(inti = 0; i < fs.length; i++) { System.out.print(fs[i]);if(i < fs.length - 1) System.out.print(" + "); } System.out.print(" = "); Fraction total =newFraction(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

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!

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.

importjava.io.*;importjava.util.*;importjava.util.regex.*;publicclassTuringMachine {privatefinalstaticPattern statesPattern = Pattern.compile("states \\{ (.*) \\} initial \"(\\w+)\"");privatefinalstaticPattern alphabetPattern = Pattern.compile("alphabet \\{ *(.*) *\\} blank '(.)'");privatefinalstaticPattern transPattern = Pattern.compile("trans from \"(.*)\" to \"(.*)\" on \\('(.)'\\) "+"write '(.)' move (right|left)");privatestaticfinalState HALT =newState("Halt");privatestaticclassState {privatefinalString name;privatefinalMap<Character, Transition> transitions =newHashMap<>(); State(String name) {this.name = name; }publicString toString() {returnname; }publicvoidaddTransition(Transition transition) {if(transition.from !=this) {thrownewIllegalArgumentException(); } transitions.put(transition.read, transition); }publicTransition getTransition(charread) {returntransitions.get(read); } }privatestaticenumMove { left, right; }privatestaticclassTransition {privatefinalState from, to;privatefinalcharread;privatefinalcharwrite;privatefinalMove move; Transition(State from, State to,charread,charwrite, Move move) {this.from = from;this.to = to;if(this.from ==null)thrownewNullPointerException();if(this.to ==null)thrownewNullPointerException();this.read = read;this.write = write;this.move = move; }publicString toString() {return"trans from \""+ from +"\" to \""+ to +"\" "+"on ('"+ read +"') write '"+ write +"' "+"move "+ move; } }privatefinalState initial;privatefinalcharblank;privateTuringMachine(State initial,charblank) {this.initial = initial;this.blank = blank; }publicCharSequence execute(CharSequence input) { State state = initial; StringBuilder tape =newStringBuilder(input);intpos = 0;while(state != HALT) { System.out.println(">>> "+ tape); System.out.println(space(pos + 4) +"^"+ space(Math.max(50 - pos, 10)) + state);charread = tape.charAt(pos); Transition transition = state.getTransition(read);if(transition ==null) {thrownewIllegalStateException("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; }returntape; }privateString space(intlength) {char[] spaces =newchar[length]; Arrays.fill(spaces, ' ');returnnewString(spaces); }publicstaticTuringMachine create(String program)throwsIOException { BufferedReader in =newBufferedReader(newStringReader(program) ); String line; Map<String, State> states =newHashMap<>(); states.put("Halt", HALT); State initial =null; Character blank =null; Set<Character> alphabet =newLinkedHashSet<>();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);booleanopeningquoteseen =false;for(inti = 0; i < chars.length(); i++) {if(openingquoteseen) { alphabet.add(chars.charAt(i)); openingquoteseen =false; i++; }elseif(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) {thrownewIllegalArgumentException("undefined state \"" + matcher.group(1) +"\""); } State to = states.get(matcher.group(2));if(to ==null) {thrownewIllegalArgumentException("undefined state \""+ matcher.group(2) +"\""); }charread = matcher.group(3).charAt(0);if(!alphabet.contains(read)) {thrownewIllegalArgumentException("alphabet does not contain '"+ read +"'"); }charwrite = matcher.group(4).charAt(0);if(!alphabet.contains(write)) {thrownewIllegalArgumentException("alphabet does not contain '"+ write +"'"); } String move = matcher.group(5); Transition transition =newTransition(from, to, read, write, Move.valueOf(move)); from.addTransition(transition);continue; }if(!line.isEmpty() && !line.startsWith("\\s*//")) {thrownewIllegalStateException("Unrecognized line: "+ line); } }returnnewTuringMachine(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:

importjava.io.*;importjava.util.*;importjava.util.regex.*;publicclassTuringMachineSubtract {publicstaticvoidmain(String... args)throwsIOException { 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="); }privatestaticvoidtest(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:

importjava.io.*;publicclassTuringMachineAdd {publicstaticvoidmain(String... args)throwsIOException { 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="); }privatestaticvoidtest(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, 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.

importjava.io.*;publicclassTuringMachineUniversal {publicstaticvoidmain(String... args)throwsIOException { 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"); }privatestaticvoidtest(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

Book Review Articles Related Java Course

Would you like to receive our monthly Java newsletter, with lots of interesting tips and tricks that will make you a better Java programmer?