The Java Specialists' Newsletter
Issue 21620131230
Category:
Book Review
Java version: Java 7 Book Review: Good Mathby Dr. Heinz M. KabutzAbstract: 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:
We have revised our "Advanced Topics" course, covering Reflection, Java NIO, Data Structures, Memory Management and several other useful topics for Java experts to master. 2 days of extreme fun and learning. Extreme Java  Advanced Topics.
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 firstyear 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 longterm storage in my brain.
One of the particularly interesting sections was on continued
fractions. Since the author Mark ChuCarroll 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
nonone 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,
ChuCarroll 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 twostate, threesymbol 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 11111111111111111=111, or 107=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 final static Pattern statesPattern = Pattern.compile(
"states \\{ (.*) \\} initial \"(\\w+)\""
);
private final static Pattern alphabetPattern = Pattern.compile(
"alphabet \\{ *(.*) *\\} blank '(.)'"
);
private final static Pattern transPattern = Pattern.compile(
"trans from \"(.*)\" to \"(.*)\" on \\('(.)'\\) " +
"write '(.)' move (rightleft)"
);
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, "1111111111111=");
test(tm, "111111111111=");
test(tm, "1111111111=");
test(tm, "1111111=");
test(tm, "111111=");
}
private static void test(TuringMachine tm, CharSequence input) {
System.out.println(input + " => " + tm.execute(input));
}
}
For example, here is 1111111= executed on our Turing Machine:
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111=
^ scan
>>> 1111111
^ erase1
>>> 111111=
^ subtract1
>>> 111111=
^ subtract1
>>> 111111=
^ 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
1111111= => 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, 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
Book Review Articles
Related Java Course
