[FOM] Quadruples instead of quintuples in TM's
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"
"Computability: Computable Functions, Logic and the Foundations of
Mathematics" (R. L. Epstein &W. A. Carnielli) using quadruples
instead of quintuples.
More information about the FOM