** Next:** More functions than procedures
** Up:** Procedures and Functions
** Previous:** Procedures and Functions

A procedure is equivalent to a TM, and all TM's can be encoded as
finite binary strings [Hopcroft, Section 8.3]. This means that the
set of TM's encoded in binary is a subset of the integers encoded in
binary (not all binary integers code for a TM). For this reason, the
members of the set of integers can be put in a one-to-one
correspondence with the members of the set of TMs (procedures).

*root*

*6/10/1998*