[FOM] Turing machines: quadruples vs quintuples

[Martin Davis]

In connection with Harvey Friedman's recent postings Bob Solovay wrote:

<<I'm puzzled by the use of "quadruples" here. Usually TM's are
presented with quintuples:

{State, Symbol} --> {New State, New Symbol, Direction to shift}.

If I had to guess, I'd suspect that in the quadruple, either a
direction to shift *or* a new symbol to print is included as the last
component.

Any reason behind the shift from quintuples to quadruples?>>

First Bob's guess is exactly right.

Post used the quadruple version in his 1947 paper: "Recursive Unsolvability 
of a Problem of Thue". He explained to me (I was his student as an 
undergraduate when that paper was published) that he found the quadruple 
formulation more "fundamental" (a word he was fond of) because each machine 
operation involved one thing instead of two.

When I wrote my "Computability & Unsolvability" I decided to follow Post.

Martin


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com