Noncomputable Functions

This week, we focused mainly on noncomputable functions and the fact that problems exist for which you cannot write an algorithm to solve.  For instance, you can't check whether a given function will be caught in an infinite loop with a specific input using another function - how would it tell the difference between infinite and really really long?  There would have to be some kind of time constraint on the checking function, and so it wouldn't return the correct answer all of the time.

Noncomputable functions are functions for which we can say what f(x) is for every x, but we can't explain how to compute that.  They are impossible to code, and we can't extend other functions to cover them.  However, if we know that a function is noncomputable we can use it to prove that another function is as well - if we could theoretically extend another function to build the original, the other function is also unwriteable:

g computable -> f computable through extension

gives as a contrapositive

f non-computable -> g non-computable

which is a contradiction, so must be false