Question

We say that a function is computable if there is a computer program that finds the values of this function. UseExercises37 and 38to show that there are functions that are not computable.

Short answer

There are more functions than computer programs to compute them.

Step-by-step solution

Step 1L

Exercise 37 :

The set of all computer program is countable.

Step 2:

Exercise 38 :

The set of all functions from the positive integers to $\left\{0,1,2,3,4,5,6,7,8,9\right\}$is uncountable.

Step 3:

Therefore, there are some functions which are not computable.

There are more functions than computer programs to compute them.