next up previous contents
Next: Problems Up: Procedures and Functions Previous: Procedures equivalent to TM's

More functions than procedures

The set of functions mapping integers into the set 0,1 is at least as large as the set of real numbers (consider $f(i)=\bmod (i*j,2)\
\forall\ j \in \mathbf{I}$). 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].