Wednesday, February 28, 2007

My First Turing Machine™

So yesterday I got to design my first Turing machine. It was a lot of fun. The machine would start with a string of 1s and 0s such as █111111101111█. It is some number of 1s followed by a single 0 followed by another series of 1s. Then it would exit in one of two final states depending on which of the two sets of 1s is larger. On the ends are markers indicating the edge of meaningful data.

In case you're curious how such a machine would work, I'll be happy to list the states and transitions for you. The first value is the value read from the tape. The second is the value that is written back to the same place on the tape. The third value is the state that the machine transitions to, and the fourth value tells whether the read/write head should move right or left. The machine begins and ends with the r/w head on the first non-█ character in the tape, and final state f1 means that the first set of 1s is greater than or equal to the second set. Conversely, final state f2 means that the second set is greater. Why am I putting this up? Because I'm procrastinating from sleep and this makes me look like I'm doing important work or something. I'm really not. (-:

Good night, all!
  • State a
    • 1, X, b, R
    • 0, 0, g, R
    • X, X, a, R
  • State b
    • 1, 1, b, R
    • 0, 0, c, R
  • State c
    • 1, X, d, R
    • X, X, c, R
  • State d
    • 1, 1, f, L
    • 0, 0, f, L
    • █, █, e, L
    • X, X, f, L
  • State e
    • 1, 1, e, L
    • 0, 0, e, L
    • X, 1, e, L
    • █, █, f1, R
  • State f
    • 1, 1, f, L
    • 0, 0, f, L
    • X, X, f, L
    • █, █, a, R
  • State g
    • 1, 1, g, R
    • 0, 0, g, R
    • X, X, g, R
    • █, █, h, L
  • State h
    • 1, 1, h, L
    • 0, 0, h, L
    • X, 1, h, L
    • █, █, f2, R

No comments: