November, Week 10

The main theme of this week was the finite-state automatas and deterministic finite-state automatas (I wrote full names on purpose, so that this slog entry appears bigger. This remark is written for the same reason). Finite state machines are a very interesting topic, and I actually find it pretty amazing that a machine that performs a single transition based on a finite state it is in, and the data it sees, can do some pretty amazing stuff (like determining if a string is a multiple of 3 in base 2 or not). Consider a Turing machine. Although it is not exactly what we studied in class, it has many similarities with a DFSA. A 5-tuple Turing has instructions in the form of (q, ss, sp, dir, q'), where q and q' are states, ss and sp are symbols (e.g. '1' or '0'), and dir is direction to move the tape (left or right). This 5-tuple basically translates as


if (current state == q)
{
if (see symbol ss)
{
erase ss and print symbol sp in its place;
move tape in direction dir;
current state = q';
}
}

As simple as this machine is, it is actually able to simulate the logic of any computer algorithm.
First I couldn't believe it, but it turns out that it is actually true. I started researching and I wanted to find an RSA encryption algorithm written on a Turing machine (most likely a 1000+ page text file of state invariants), but I was not able to find one.