chap limits to computation ( ( ( ( figure an illustration of assigning functions to bins can we assign every function to binthe answer is nobecause there is always way to create new function that is not in any of the bins suppose that somebody presents way of assigning functions to bins that they claim includes all of the functions we can build new function that has not been assigned to any binas follows take the output value for input from the function in the first bin call this value ( add to itand assign the result as the output of new function for input value regardless of the remaining values assigned to our new functionit must be different from the first function in the tablebecause the two give different outputs for input now take the output value for from the second function in the table (known as ( )add to this value and assign it as the output for in our new function thusour new function must be different from the function of bin because they will differ at least at the second value continue in this mannerassigning fnew (ifi ( for all values thusthe new function must be different from any function fi at least at position this procedure for constructing new function not already in the table is called diagonalization because the new function is different from every other functionit must not be in the table this is true no matter how we try to assign functions to binsand so the number of integer functions is uncountable the significance of this is that not all functions can possibly be assigned to programsso there must be functions with no corresponding program figure illustrates this argument the halting problem is unsolvable while there might be intellectual appeal to knowing that there exists some function that cannot be computed by computer programdoes this mean that there is any such useful functionafter alldoes it really matter if no program can compute "nonsensefunction such as shown in bin of figure now we will prove