next up previous contents
Next: More functions than procedures Up: Procedures and Functions Previous: Procedures and Functions

Procedures equivalent to TM's

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).