[FOM] Turing machines: quadruples vs quintuples

Martin Davis martin at eipye.com
Tue Feb 24 01:16:46 EST 2004

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

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 Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)

More information about the FOM mailing list