[FOM] Quadruples instead of quintuples in TM's

Walter Carnielli carniell at cle.unicamp.br
Thu Feb 26 13:18:51 EST 2004

Solovay says he  is  puzzled  by the  use of quadruples  instead of
quintuples in TM's, and asks for a  reason.  I just want to add to the
explanation Davis offered that  experience in  teaching Computability
shows that the use of quadruples makes it much more palatable to
students to understand instructions for TM´s as a programming language.

The "quadruples" presentation makes possible to quickly construct the
first recursive functions  as TM´s, and to appreciate the
use of  arithmetical descriptions which eventually reaches Gödel´s
theorems. That´s why we followed Davis´ "Computability & Unsolvability"
in our
"Computability: Computable Functions, Logic and the Foundations of
Mathematics" (R. L. Epstein &W. A. Carnielli) using quadruples
instead of  quintuples.

Walter Carnielli

More information about the FOM mailing list