Next: Problems
Up: Procedures and Functions
Previous: Procedures equivalent to TM's
The set of functions mapping integers into the set 0,1 is at least
as large as the set of real numbers (consider
). Since the set of integers cannot be put
in one-to-one correspondence with the set of reals, there exist
functions for which there are no corresponding procedures. This is
important because it means that some functions can not be computed
[Hopcroft, p. 147].
root
6/10/1998