Martin Geisler Online

Ahh, there’s just a single day left until the Easter holidays start, and I’m only having three hours tomorrow accourding to my schedule!

Not that I’ve been studying all that much the last couple of days… I sat down yesterday and tried to make the Turing Machine that would take an input tape with “aaaaaa#aaaaaaaaa” and turn it into “aaa“.

In other words: calculate the greatest common divisor of m and n represented by the input a^m#a^n. In the above case, the greatest common divisor of 6 and 9 is 3 if I’m not mistaken.

It turned out that Turing Machines are extremely annoying to program! Even the simplest operation gets enormously complicated. Somehow I managed to sit up all night trying to get things to work — I just kept tweeking and changing my program, hoping to catch that finaly special case that ruined the result. Amazingly I didn’t get that tired, it’s as if you reach a point and from then on you can carry on. But I still have a bad feeling that I’m going to get really tired soon…

I used a rather nice program called gturing to test my program, which you can find here. The comments are in Danish, sorry about that, but I used the program in a Danish hand-in exercise and when I rewrote things this morning I changed the English comments into Danish ones so that they would be easier to use in the report. I believe that the program now handles all correct input correctly. Correct input is input that matches the RegularExpression “a^m#a^n”.

The program also handles cases like “#“, “aaa#“, and “#aaa“. With the first input the machine calculates gcd(0, 0) = 0, the two other inputs represent gcd(3, 0) = gcd(0, 3) = 3. The reason why gcd(0, 0) = 0 is, that gcd(m, n) is defined as the unique whole number d that satisfies

Div(d) = Div(m) intersect Div(n)

where Div(n) = { d in N | d divides n }. Here we have that Div(0) = N, that is, all natural numbers divide 0 — take a natural number and multiply it with 0 to see for your self. So we look for a number d that satisfies that Div(d) = N. The only number that has this property is 0 itself, so this means that gcd(0, 0) = 0.