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