ThePanda

Edit: Now updated with link to picture

This has been bothering me since yesterday, and were it not for people in the CS department e-mailing me stuff, it would still bother me. Nothing very deep about this, but it's an interesting difference in notation.

Yesterday afternoon, EAS, my cubemate, was looking at a Facebook photograph of someone who had the 7-tuple formal representation for a Turing machine tattooed on their body. That's OK, people tend to have interesting tattoos. What threw me off about this picture however was the fact that the tuple looked different from what my memory was serving up, and this is bad since one does hope that nearly a semester's worth of sitting in on classes, and a semester's worth of TAing a course would at least leave me with a not so wrong memory of what these tuples are, even though admittedly they don't show up all that often on assignments or such.

The problem of course was that Wikipedia seemed to agree with her tattooed tuple, and Turing's paper makes no mention of the tuple so there isn't really so much of a historically accurate version. The wikipedia tuple is:

Where the symbols represent:
Q: Set of all states
Gamma: Tape alphabets
b: Blank tape symbol, is in gamma
Sigma: Tape input alphabets
Delta: Transition function
q_0: Start state
F: Set of final states (Wikipedia notes that they may be accepting states)

So earlier today JKF responded to my e-mail with a copy of the second cs051 lecture, and the 51 tuple is:

Where the symbols represent:
Q: Set of all states
Gamma: Tape alphabets
Sigma: Tape input alphabets
Delta: Transition function
q_0: Start state
q_a: Accepting state
q_r: Rejecting state

Now I am pretty sure this is the Sipser version of the 7-tuple, while Wikipedia claims, and other webpages seem to support the theory that the wikipedia 7 tupple comes from Hopcroft and Ullman. Both are textbooks, and were first published in the same decade (Sipser in 1973, Hopcroft and Ullman in 1979), and both seem to be the driving force behind people's impressions on what the 7-tuple should be, and both at some level seem to be correct in why their formalism works. For the wikipedia one, accepts and rejects make little sense, since you can just ascribe meanings to states within F, and consider one to be q_r or similar. The halting problem doesn't change much, though Sipser's ATM (the accepting turing machine) no longer makes sense, and must be modified to FTM. The blank tape symbol adds some formalism, since while Turing's description spoke of the idea of blank squares, he didn't really ascribe it form, and instead described it as something the head could read and tell you. This just jumps from having an intelligent head to a machine which figures these things out for itself.

At the same time, Sipser's model also makes sense, since intelligent heads don't really add much, you don't need multiple finish states (hint just connect all of them to q_a, or q_r using an empty transition), and having only accepts and rejects moves information which could be intrinsically contained in the states out onto the tape. Since universal turing machines already make that leap, this wouldn't really be bad.

That being said, I question why there is a 7-tuple at all, clearly a 6-tuple with only one final state is capable of representing just as much information (if you reject write it down on the tape),and intelligent heads get rid of the blank tape symbol. I am aware that formal definitions of Turing machines don't show up that often, but it is unusual to find two differing formalisms of the same size, both omitting different pieces of what could be considered redundant information.

Panda

This entry was posted on Thursday, August 2nd, 2007 at 10:11 am and is filed under CS, formalism, math, turing machine. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.